{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sort an Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #divide-and-conquer #bucket-sort #counting-sort #radix-sort #sorting #heap-priority-queue #merge-sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #分治 #桶排序 #计数排序 #基数排序 #排序 #堆（优先队列） #归并排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sortArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #排序数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>nums</code>，请你将该数组升序排列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<ol>\n",
    "</ol>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [5,2,3,1]\n",
    "<strong>输出：</strong>[1,2,3,5]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [5,1,1,2,0,0]\n",
    "<strong>输出：</strong>[0,0,1,1,2,5]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>-5 * 10<sup>4</sup> &lt;= nums[i] &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sort-an-array](https://leetcode.cn/problems/sort-an-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sort-an-array](https://leetcode.cn/problems/sort-an-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,2,3,1]', '[5,1,1,2,0,0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        def swap(nums: List[int], t1: int, t2: int):\n",
    "            t = nums[t1]\n",
    "            nums[t1] = nums[t2]\n",
    "            nums[t2] = t\n",
    "\n",
    "        def partition(nums: List[int], left: int, right: int) -> (int, int):\n",
    "            num = nums[right]\n",
    "            cur = left\n",
    "            while cur <= right:\n",
    "                if nums[cur] < num:\n",
    "                    swap(nums, cur, left)\n",
    "                    left += 1\n",
    "                    cur = left\n",
    "                elif nums[cur] > num:\n",
    "                    swap(nums, cur, right)\n",
    "                    right -= 1\n",
    "                else:\n",
    "                    cur += 1\n",
    "            return [left, right]\n",
    "\n",
    "        def sort_process(nums: List[int], left: int, right: int) -> None:\n",
    "            if left >= right:\n",
    "                return\n",
    "            x = random.randint(left, right)\n",
    "            swap(nums, right, x)\n",
    "            m1, m2 = partition(nums, left, right)\n",
    "            sort_process(nums, left, m1 - 1)\n",
    "            sort_process(nums, m2 + 1, right)\n",
    "\n",
    "        sort_process(nums, 0, len(nums) - 1)\n",
    "\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import random\r\n",
    "class Solution:\r\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\r\n",
    "        def heapify(heap:list,root:int,hlen:int):\r\n",
    "            p=root\r\n",
    "            while p*2+1<hlen:\r\n",
    "                l,r=2*p+1,2*p+2\r\n",
    "                if r<hlen and heap[r]>heap[l]:\r\n",
    "                    nxt=r\r\n",
    "                else:\r\n",
    "                    nxt=l\r\n",
    "                if heap[p]<heap[nxt]:\r\n",
    "                    heap[p],heap[nxt]=heap[nxt],heap[p]\r\n",
    "                    p=nxt\r\n",
    "                else:\r\n",
    "                    break\r\n",
    "\r\n",
    "        l=len(nums)\r\n",
    "        for i in range(l-1,-1,-1):\r\n",
    "            heapify(nums,i,l)\r\n",
    "\r\n",
    "        for i in range(l-1,-1,-1):\r\n",
    "            nums[i],nums[0]=nums[0],nums[i]\r\n",
    "            heapify(nums,0,i)\r\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        return self.mergeSort(nums, 0, len(nums) - 1)\n",
    "\n",
    "    def mergeSort(self, arr, start, end):\n",
    "        if end -start + 1 <= 1:\n",
    "            return arr\n",
    "        mid = (end + start) // 2\n",
    "        self.mergeSort(arr, start, mid)\n",
    "        self.mergeSort(arr, mid + 1, end)\n",
    "        self.merge(arr, start, mid, end)\n",
    "        return arr\n",
    "    \n",
    "    def merge(self, arr, start, mid, end):\n",
    "        left = arr[start: mid + 1]\n",
    "        right = arr[mid + 1: end + 1]\n",
    "\n",
    "        i, j = 0, 0\n",
    "        k = start\n",
    "        while i < len(left) and j < len(right):\n",
    "            if left[i] <= right[j]:\n",
    "                arr[k] = left[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                arr[k] = right[j]\n",
    "                j += 1\n",
    "            k += 1\n",
    "        while i < len(left):\n",
    "            arr[k] = left[i]\n",
    "            k += 1\n",
    "            i += 1\n",
    "        while j < len(right):\n",
    "            arr[k] = right[j]\n",
    "            j += 1\n",
    "            k += 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        MIN_MERGE = 32\n",
    "\n",
    "        # 对32个元素序列进行插入排序\n",
    "        # 对nums 左闭右闭 [left, right] 范围内数据进行插入排序\n",
    "        def insertion_sort(nums, left, right):\n",
    "            for i in range(left+1, right+1):\n",
    "                cur = i\n",
    "                while cur > left and nums[cur] < nums[cur - 1]:\n",
    "                    nums[cur], nums[cur-1] = nums[cur-1], nums[cur]\n",
    "                    cur -= 1\n",
    "\n",
    "        # 归并[start, mid] [mid+1, end]\n",
    "        def merge(nums, start, mid, end):\n",
    "            left_aux = list()\n",
    "            # 左闭右闭[start, mid]\n",
    "            for i in range(start, mid + 1):\n",
    "                left_aux.append(nums[i])\n",
    "            \n",
    "            left, left_end = 0, mid + 1 - start\n",
    "            right, right_end = mid + 1, end + 1\n",
    "            k = start\n",
    "            while left < left_end:\n",
    "                if right < right_end and nums[right] < left_aux[left]:\n",
    "                    nums[k] = nums[right]\n",
    "                    right += 1\n",
    "                else:\n",
    "                    nums[k] = left_aux[left]\n",
    "                    left += 1\n",
    "                k += 1\n",
    "\n",
    "        def time_sort(nums):\n",
    "            n = len(nums)\n",
    "            \n",
    "            # 以 MIN_MERGE=32为步长进行遍历，32个元素进行插入排序\n",
    "            for start in range(0, n, MIN_MERGE):\n",
    "                # 防止不满32个元素时，索引越界 min(start + MIN_MERGE - 1, n - 1)\n",
    "                # [0, 31]为32个元素，因为索引从0开始，所以 start + MIN_MERGE - 1 表示右边界，保证有32个元素\n",
    "                insertion_sort(nums, start, min(start + MIN_MERGE - 1, n - 1))\n",
    "            \n",
    "            # 归并\n",
    "            #   以 size=2 * 32 = 64为步长，两两合并64内的两个有序的32，一直到n\n",
    "            # 再以 size=2 * 64 = 128为步长，两两合并128内的两个有序的64，一直到n\n",
    "            # 步长一直到 size>=n结束\n",
    "            \n",
    "            \n",
    "            size = MIN_MERGE\n",
    "            while size < n:\n",
    "                for left in range(0, n, 2 * size):\n",
    "                    # size个长度，左边界 left, 中间 left+size-1, 右边界 left+2*size-1\n",
    "                    # 防止元素个数超出size个，取和 n-1的最小值\n",
    "                    mid = min(n-1, left + size - 1) \n",
    "                    right = min(n-1, left + 2 * size -1)\n",
    "                    \n",
    "                    # 确保 mid < right 再进行合并\n",
    "                    if mid < right:\n",
    "                        merge(nums, left, mid, right)\n",
    "                \n",
    "                # 更新size 32->64...\n",
    "                size  = 2 * size\n",
    "        time_sort(nums)\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        def sort_function(nums, start, mid, end):\n",
    "            left = start\n",
    "            right = mid+1\n",
    "            temp = []\n",
    "\n",
    "            while left<=mid and right<=end:\n",
    "                if nums[left]<nums[right]:\n",
    "                    temp.append(nums[left])\n",
    "                    left+=1\n",
    "\n",
    "                else:\n",
    "                    temp.append(nums[right])\n",
    "                    right+=1\n",
    "            temp.extend(nums[left:mid+1])\n",
    "            temp.extend(nums[right:end+1])\n",
    "            for i in range(start, end+1):\n",
    "                nums[i] = temp[i-start]\n",
    "\n",
    "        def execute_sort(nums, start, end):\n",
    "            if start>=end:\n",
    "                return \n",
    "\n",
    "            mid = (start+end)//2\n",
    "            execute_sort(nums, start, mid)\n",
    "            execute_sort(nums, mid+1, end)\n",
    "            sort_function(nums, start, mid, end)\n",
    "\n",
    "        execute_sort(nums, 0, len(nums)-1)\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "   \n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        def merge(nums,left,mid,right):\n",
    "            tmp= []\n",
    "            mid= left+(right-left)//2\n",
    "            p1,p2=left,mid+1\n",
    "            \n",
    "            while p1<=mid and p2<=right:\n",
    "                if nums[p1]>nums[p2]:\n",
    "                    tmp.append(nums[p2])\n",
    "                    p2+=1\n",
    "                else:\n",
    "                    tmp.append(nums[p1])\n",
    "                    p1+=1\n",
    "\n",
    "            if p1<=mid:\n",
    "                tmp.extend(nums[p1:mid+1])\n",
    "            if p2<=right:tmp.extend(nums[p2:right+1])\n",
    "            nums[left:right+1]=tmp\n",
    "\n",
    "        def process(arr,left,right):\n",
    "            if left ==right:\n",
    "                return\n",
    "\n",
    "            mid=left+(right-left)//2\n",
    "            process(arr,left,mid)\n",
    "            process(arr,mid+1,right)\n",
    "            merge(arr,left,mid,right)\n",
    "\n",
    "        left ,right = 0,len(nums)-1\n",
    "        process(nums,left,right)\n",
    "        return nums\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "            \n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "\n",
    "        self.CountSort(nums)\n",
    "        return nums\n",
    "\n",
    "       \n",
    "    def BubbleSort(self, nums: List[int]) -> List[int]:\n",
    "        N = len(nums)\n",
    "        for i in range(N-1, 0, -1):\n",
    "            for j in range(0, i):\n",
    "                if nums[j] > nums[j+1]:\n",
    "                    nums[j], nums[j+1] = nums[j+1], nums[j]\n",
    "        return\n",
    "\n",
    "    def SelectSort(self, nums: List[int]) -> List[int]:\n",
    "        N = len(nums)\n",
    "        for i in range(0,N-1):\n",
    "            min_index = i \n",
    "            for j in range(i+1, N):\n",
    "                min_index = j if nums[j] < nums[min_index] else min_index\n",
    "            if i != min_index:\n",
    "                nums[min_index], nums[i] = nums[i], nums[min_index]\n",
    "        return \n",
    "\n",
    "    def InsertSort(self, nums: List[int]) -> List[int]:\n",
    "        N = len(nums)\n",
    "        for i in range(1,N):\n",
    "            for j in range(i-1,-1,-1):\n",
    "                if nums[j] > nums[j+1]:\n",
    "                    nums[j], nums[j+1] = nums[j+1],nums[j]\n",
    "        return \n",
    "\n",
    "    def ShellSort(self, nums: List[int], d: int) -> List[int]:\n",
    "        N = len(nums)\n",
    "        gap = 1\n",
    "        while gap < N // d:\n",
    "            gap = gap*d + 1\n",
    "        while gap > 0:\n",
    "            for i in range(gap, N):\n",
    "                for j in range(i-gap, -1, -gap):\n",
    "                    if nums[j] > nums[j+gap] :\n",
    "                        nums[j], nums[j+gap] = nums[j+gap], nums[j]\n",
    "            gap = gap // d\n",
    "        return \n",
    "        \n",
    "    def MergeSort(self, nums: List[int], L: int, R:int) -> List[int]:\n",
    "        if L >= R:\n",
    "            return \n",
    "        M = L + (R-L)//2\n",
    "        self.MergeSort(nums, L, M)\n",
    "        self.MergeSort(nums, M+1, R)\n",
    "\n",
    "        p1, p2 = L, M+1\n",
    "        tmp = []\n",
    "        while p1 <=M and p2 <=R:\n",
    "            if nums[p1]<=nums[p2]:\n",
    "                tmp.append(nums[p1])\n",
    "                p1+=1\n",
    "            else:\n",
    "                tmp.append(nums[p2])\n",
    "                p2+=1\n",
    "        while p1<=M:\n",
    "            tmp.append(nums[p1])\n",
    "            p1+=1\n",
    "        while p2 <=R:\n",
    "            tmp.append(nums[p2])\n",
    "            p2+=1\n",
    "        \n",
    "        for k in range(len(tmp)):\n",
    "            nums[L+k]=tmp[k]\n",
    "        return\n",
    "\n",
    "    def HeapSort_1(self, nums:List[int]) -> List[int]:\n",
    "        def HeapInsert(nums, index):\n",
    "            father = int((index-1)/2)\n",
    "            while nums[index]> nums[father]:\n",
    "                nums[index], nums[father] = nums[father], nums[index]\n",
    "                index = father\n",
    "                father = int((index-1)/2)\n",
    "            return \n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            HeapInsert(nums, i)\n",
    "        print(nums,\"---\")\n",
    "        \n",
    "        def Heapify(nums, index, border):\n",
    "            left = 2*index + 1\n",
    "            while left<=border:\n",
    "                right = left+1\n",
    "                large = right if right<=border and nums[right] > nums[left] else left \n",
    "                large = index if nums[index] >= nums[large] else large\n",
    "                if large == index:\n",
    "                    break\n",
    "                else:\n",
    "                    nums[index], nums[large] = nums[large], nums[index]\n",
    "                    index = large \n",
    "                    left = 2*index + 1\n",
    "            return \n",
    "\n",
    "        N = len(nums)\n",
    "        for i in range(N-1, 0, -1):\n",
    "            print(nums)\n",
    "            nums[0], nums[i] = nums[i], nums[0]\n",
    "            Heapify(nums, 0, i-1)\n",
    "\n",
    "        return \n",
    "\n",
    "\n",
    "    def HeapSort_2(self, nums:List[int]) -> List[int]:\n",
    "        def Heapify(nums, index, length):\n",
    "            # 把小的数往下沉，恢复成大根堆\n",
    "            left = 2*index+1\n",
    "            while left <= length:\n",
    "                right = left+1\n",
    "                large = right if right<=length and nums[right] > nums[left] else left \n",
    "                large = index if nums[index] > nums[large] else large \n",
    "                if large == index:\n",
    "                    break\n",
    "                else:\n",
    "                    nums[large], nums[index] = nums[index], nums[large]\n",
    "                    index = large \n",
    "                    left = 2*index+1\n",
    "            return \n",
    "\n",
    "        N = len(nums)\n",
    "        for i in range(int(N/2), -1, -1):\n",
    "            Heapify(nums, i , N-1)\n",
    "        \n",
    "        for i in range(N-1, 0, -1):\n",
    "            nums[0], nums[i] = nums[i], nums[0]\n",
    "            Heapify(nums, 0, i-1)\n",
    "\n",
    "        return \n",
    "\n",
    "\n",
    "    def CountSort(self, nums):\n",
    "\n",
    "        max_v = max(nums)\n",
    "        min_v = min(nums)\n",
    "        bias = max(0, -min_v)\n",
    "\n",
    "        count_list = [0]*(max_v+bias+1)\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            count_list[nums[i]+bias]+=1\n",
    "\n",
    "        j = 0\n",
    "        for k in range(max_v+bias+1):\n",
    "            while count_list[k]>0:\n",
    "                nums[j] = k-bias\n",
    "                count_list[k] -= 1\n",
    "                j+=1\n",
    "        \n",
    "        return \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        self.merge_sort(nums, 0, len(nums) - 1)\n",
    "        return nums\n",
    "\n",
    "    def merge_sort(self, nums, l, r):\n",
    "        if l < r:\n",
    "            mid = (l + r) // 2\n",
    "            self.merge_sort(nums, l, mid)\n",
    "            self.merge_sort(nums, mid + 1, r)\n",
    "            tmp = []\n",
    "            i = l\n",
    "            j = mid + 1\n",
    "            while i <= mid or j <= r:\n",
    "                if j > r or (i <= mid and nums[i] <= nums[j]):\n",
    "                    tmp.append(nums[i])\n",
    "                    i = i + 1\n",
    "                else:\n",
    "                    tmp.append(nums[j])\n",
    "                    j = j + 1\n",
    "            nums[l : r + 1] = tmp\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        def pivot(nums, l, r):\n",
    "            if l >= r:\n",
    "                return\n",
    "            import random\n",
    "            x = nums[random.randint(l,r)]\n",
    "            i = l\n",
    "            j = r\n",
    "            while ( i <= j ):\n",
    "                while (nums[i] < x ):\n",
    "                    i += 1\n",
    "                while (nums[j] > x ):\n",
    "                    j -= 1\n",
    "                if i <= j:\n",
    "                    nums[i],nums[j] = nums[j],nums[i]\n",
    "                    i+=1\n",
    "                    j-=1\n",
    "            if r>i:\n",
    "                pivot(nums, i, r)\n",
    "            if j>l:\n",
    "                pivot(nums, l, j)\n",
    "        pivot(nums, 0, len(nums)-1)\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        # 堆排序\n",
    "        def max_heapify(heap, p, heap_size):\n",
    "            largest = p \n",
    "            l, r = 2*p+1, 2*p+2\n",
    "            \n",
    "            if l < heap_size and heap[l] > heap[p]:\n",
    "                largest = l \n",
    "            if r < heap_size and heap[r] > heap[largest]:\n",
    "                largest = r\n",
    "            if largest != p: \n",
    "                heap[largest], heap[p] = heap[p], heap[largest]\n",
    "                max_heapify(heap, largest, heap_size)\n",
    "            pass \n",
    "\n",
    "        def build_heap(heap):\n",
    "            n = len(heap)\n",
    "            for i in range(n//2, -1, -1):\n",
    "                max_heapify(heap, i, n)\n",
    "\n",
    "        \n",
    "        def max_heap_sort(heap):\n",
    "            build_heap(heap)\n",
    "            n = len(heap)\n",
    "            for i in range(n-1, -1, -1):\n",
    "                heap[0], heap[i] = heap[i], heap[0]\n",
    "                max_heapify(heap, 0, i)\n",
    "\n",
    "             \n",
    "        max_heap_sort(nums)\n",
    "        return nums "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        if len(nums) <= 1:\n",
    "            return nums\n",
    "        mid = len(nums) // 2\n",
    "        # 分\n",
    "        left = self.sortArray(nums[:mid])\n",
    "        right = self.sortArray(nums[mid:])\n",
    "        # 合并\n",
    "        return self.merge(left, right)\n",
    "\n",
    "\n",
    "    def merge(self,left, right):\n",
    "        res = []\n",
    "        i = 0\n",
    "        j = 0\n",
    "        while i < len(left) and j < len(right):\n",
    "            if left[i] <= right[j]:\n",
    "                res.append(left[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                res.append(right[j])\n",
    "                j += 1\n",
    "        res += left[i:]\n",
    "        res += right[j:]\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        def merge(left:List[int],right:List[int]):\n",
    "            result,i,j = [],0,0\n",
    "            while i < len(left) and j < len(right):\n",
    "                if left[i] > right[j]:\n",
    "                    result.append(right[j])\n",
    "                    j += 1\n",
    "                else:\n",
    "                    result.append(left[i])\n",
    "                    i += 1\n",
    "            while i < len(left):\n",
    "                result.append(left[i])\n",
    "                i += 1\n",
    "            while j < len(right):\n",
    "                result.append(right[j])\n",
    "                j += 1\n",
    "            return result\n",
    "        def split_merge(nums):\n",
    "            if len(nums) <= 1:\n",
    "                return nums\n",
    "            middle = len(nums)//2\n",
    "            left = split_merge(nums[:middle])\n",
    "            right = split_merge(nums[middle:])\n",
    "            return merge(left, right)\n",
    "        return split_merge(nums)\n",
    "\n",
    "\n",
    "       \n",
    "            \n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        def mergeSort(nums, l, r):\n",
    "            if l == r:\n",
    "                return\n",
    "            mid = (l + r) // 2\n",
    "            mergeSort(nums, l, mid)\n",
    "            mergeSort(nums, mid + 1, r)\n",
    "            temp = []\n",
    "            i, j = l, mid + 1\n",
    "            while i <= mid or j <= r:\n",
    "                if i > mid or (j <= r and nums[j] < nums[i]):\n",
    "                    temp.append(nums[j])\n",
    "                    j += 1\n",
    "                else:\n",
    "                    temp.append(nums[i])\n",
    "                    i += 1\n",
    "            nums[l: r + 1] = temp\n",
    "\n",
    "        mergeSort(nums, 0, len(nums) - 1)    \n",
    "        return nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import random\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        if not nums:\n",
    "            return nums\n",
    "        \n",
    "        # pivot = random.choice(nums)\n",
    "        # small = [num for num in nums if num < pivot]\n",
    "        # mid = [num for num in nums if num == pivot]\n",
    "        # big = [num for num in nums if num > pivot]\n",
    "        # return self.sortArray(small) + mid + self.sortArray(big)\n",
    "\n",
    "        def merge_sort(nums, left, right):\n",
    "            if left == right:\n",
    "                return \n",
    "            \n",
    "            mid = (left+right) // 2\n",
    "            merge_sort(nums, left, mid)\n",
    "            merge_sort(nums, mid+1, right)\n",
    "\n",
    "            tmp = []\n",
    "            i, j = left, mid+1\n",
    "            while i<=mid or j<=right:\n",
    "                if i> mid or (j<=right and nums[j]<nums[i]):\n",
    "                    tmp.append(nums[j])\n",
    "                    j += 1\n",
    "                else:\n",
    "                    tmp.append(nums[i])\n",
    "                    i += 1\n",
    "            nums[left:right+1] = tmp\n",
    "        \n",
    "        merge_sort(nums, 0, len(nums)-1)\n",
    "        return nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "\n",
    "        def partition(arr, low, high):\n",
    "            pivot = arr[low]\n",
    "            left, right = low, high\n",
    "\n",
    "            while left < right:\n",
    "                while left < right and arr[right] >= pivot:\n",
    "                    right -= 1\n",
    "                arr[left], arr[right] = arr[right], arr[left]\n",
    "                while left < right and arr[left] <= pivot:\n",
    "                    left += 1\n",
    "                arr[left], arr[right] = arr[right], arr[left]\n",
    "\n",
    "            return left\n",
    "\n",
    "        def randomPivot(arr, low, high):\n",
    "            idx = random.randint(low, high)\n",
    "            arr[idx], arr[low] = arr[low], arr[idx]\n",
    "\n",
    "            return partition(arr, low, high)\n",
    "\n",
    "        def quickSort(arr, low, high):\n",
    "            if low < high:\n",
    "                p = randomPivot(arr, low, high)\n",
    "                quickSort(arr, low, p - 1)\n",
    "                quickSort(arr, p + 1, high)\n",
    "\n",
    "        # 归并排序\n",
    "        def mergeSort(arr, low, high):\n",
    "            # 递归结束\n",
    "            if low >= high:\n",
    "                return \n",
    "\n",
    "            mid = low + (high - low) // 2\n",
    "            mergeSort(arr, low, mid)\n",
    "            mergeSort(arr, mid + 1, high)\n",
    "\n",
    "            # 数组两部分的首元素\n",
    "            left, right = low, mid+1\n",
    "            tmp = []\n",
    "            while left <= mid and right <= high:\n",
    "                if arr[left] <= arr[right]:\n",
    "                    tmp.append(arr[left])\n",
    "                    left += 1\n",
    "                else:\n",
    "                    tmp.append(arr[right])\n",
    "                    right += 1\n",
    "            \n",
    "            # 左半部分有剩\n",
    "            while left <= mid:\n",
    "                tmp.append(arr[left])\n",
    "                left += 1\n",
    "            \n",
    "            # 右半部分有剩\n",
    "            while right <= high:\n",
    "                tmp.append(arr[right])\n",
    "                right += 1\n",
    "\n",
    "            arr[low:high+1] = tmp\n",
    "        \n",
    "        # quickSort(nums, 0, len(nums)-1)\n",
    "        mergeSort(nums, 0, len(nums)-1)\n",
    "\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        if len(nums) <= 1:\n",
    "            return nums\n",
    "\n",
    "        # 分解\n",
    "        mid = len(nums) // 2\n",
    "        left_half = nums[:mid]\n",
    "        right_half = nums[mid:]\n",
    "\n",
    "        # 递归解决子问题\n",
    "        left_sorted = self.sortArray(left_half)\n",
    "        right_sorted = self.sortArray(right_half)\n",
    "\n",
    "        # 合并\n",
    "        return self.merge(left_sorted, right_sorted)\n",
    "\n",
    "    def merge(self, left: List[int], right: List[int]) -> List[int]:\n",
    "        merged = []\n",
    "        i = j = 0\n",
    "\n",
    "        # 合并两个有序数组\n",
    "        while i < len(left) and j < len(right):\n",
    "            if left[i] < right[j]:\n",
    "                merged.append(left[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                merged.append(right[j])\n",
    "                j += 1\n",
    "\n",
    "        # 将剩余的元素添加到合并数组\n",
    "        merged.extend(left[i:])\n",
    "        merged.extend(right[j:])\n",
    "\n",
    "        return merged"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        # n = len(nums)\n",
    "        # for i in range(n):\n",
    "        #     while i > 0 and nums[i-1] > nums[i]:\n",
    "        #         nums[i-1],nums[i] = nums[i],nums[i-1]\n",
    "        #         i = i - 1\n",
    "        # return nums\n",
    "\n",
    "        # n = len(nums)\n",
    "        # for i in range(n):\n",
    "        #     for j in range(1,n-i):\n",
    "        #         if nums[j-1] > nums[j]:\n",
    "        #             nums[j-1],nums[j] = nums[j],nums[j-1]\n",
    "\n",
    "        # return nums\n",
    "\n",
    "        def merge_sort(nums):\n",
    "            if len(nums) <= 1:\n",
    "                return nums\n",
    "            mid = len(nums)//2\n",
    "            left = merge_sort(nums[:mid])\n",
    "            right = merge_sort(nums[mid:])\n",
    "\n",
    "            return merge(left,right)\n",
    "\n",
    "        def merge(left,right):\n",
    "            res = []\n",
    "            i = 0\n",
    "            j = 0\n",
    "\n",
    "            while i < len(left) and j <len(right):\n",
    "                if left[i]<= right[j]:\n",
    "                    res.append(left[i])\n",
    "                    i +=1\n",
    "                else:\n",
    "                    res.append(right[j])\n",
    "                    j +=1\n",
    "            res += left[i:]\n",
    "            res += right[j:]\n",
    "\n",
    "            return res\n",
    "        return merge_sort(nums)\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        if n <= 1:\n",
    "            return nums\n",
    "        mid = n // 2\n",
    "        left = nums[:mid]\n",
    "        right = nums[mid:]\n",
    "\n",
    "        left = self.sortArray(left)\n",
    "        right = self.sortArray(right)\n",
    "        \n",
    "        i = j = k = 0\n",
    "        result = []\n",
    "        while i < len(left) and j < len(right):\n",
    "            if left[i] < right[j]:\n",
    "                result.append(left[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                result.append(right[j])\n",
    "                j += 1\n",
    "\n",
    "        while i < len(left):\n",
    "            result.append(left[i])\n",
    "            i += 1\n",
    "\n",
    "        while j < len(right):\n",
    "            result.append(right[j])\n",
    "            j += 1\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        if len(nums) == 0:\n",
    "            return []\n",
    "        q = nums[random.randint(0, len(nums)-1)]\n",
    "        left, middle, right =[], [], []\n",
    "        for nu in nums:\n",
    "            if nu < q:\n",
    "                left.append(nu)\n",
    "            elif nu > q:\n",
    "                right.append(nu)\n",
    "            else:\n",
    "                middle.append(nu)\n",
    "        leftsort = self.sortArray(left)\n",
    "        rightsort = self.sortArray(right)\n",
    "        return leftsort + middle + rightsort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "\n",
    "        def merge(nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "            l1 = 0\n",
    "            n1 = len(nums1)\n",
    "            l2 = 0\n",
    "            n2 = len(nums2)\n",
    "            ans = []\n",
    "\n",
    "            while l1 < n1 and l2 < n2:\n",
    "                if nums1[l1] <= nums2[l2]:\n",
    "                    ans.append(nums1[l1])\n",
    "                    l1 += 1\n",
    "                else:\n",
    "                    ans.append(nums2[l2])\n",
    "                    l2 += 1\n",
    "            if l1 < n1:\n",
    "                ans += nums1[l1:]\n",
    "            if l2 < n2:\n",
    "                ans += nums2[l2:]\n",
    "            return ans\n",
    "\n",
    "        def sort_process(nums: List[int], left: int, right: int) -> List[int]:\n",
    "            if left == right:\n",
    "                return [nums[left]]\n",
    "            mid = (left + right) // 2\n",
    "            left_l = sort_process(nums, left, mid)\n",
    "            right_l = sort_process(nums, mid + 1, right)\n",
    "            return merge(left_l, right_l)\n",
    "\n",
    "        return sort_process(nums, 0, len(nums) - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        if len(nums) <= 1:\n",
    "            return nums\n",
    "        pivot = random.choice(nums)\n",
    "        small = []\n",
    "        big = []\n",
    "        equal = []\n",
    "        for i in nums:\n",
    "            if i > pivot:\n",
    "                big.append(i)\n",
    "            elif i < pivot:\n",
    "                small.append(i)\n",
    "            else:\n",
    "                equal.append(i)\n",
    "        return self.sortArray(small) + equal + self.sortArray(big)\n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        if n <= 1:\n",
    "            return nums\n",
    "        pivot = random.choice(nums)\n",
    "        left = [x for x in nums if x < pivot]\n",
    "        mid = [x for x in nums if x == pivot]\n",
    "        right = [x for x in nums if x > pivot]\n",
    "        return self.sortArray(left) + mid + self.sortArray(right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        # if len(nums) <=1:\n",
    "        #     return nums\n",
    "        # plvot = random.choice(nums)\n",
    "\n",
    "        # left = self.sortArray([x for x in nums if x<plvot])\n",
    "        # right = self.sortArray([x for x in nums if x>plvot])\n",
    "\n",
    "        # mid = [x for x in nums if x == plvot]\n",
    "\n",
    "        # return left + mid + right \n",
    "        def sortArray2(nums):\n",
    "            if len(nums)<=1:\n",
    "                return nums\n",
    "            plvot = random.choice(nums)\n",
    "            left,right,mid = [],[],[]\n",
    "            for i in nums:\n",
    "                if i<plvot:\n",
    "                    left.append(i)\n",
    "                elif i>plvot:\n",
    "                    right.append(i)\n",
    "                else:\n",
    "                    mid.append(i)\n",
    "            left = sortArray2(left)\n",
    "            right = sortArray2(right)\n",
    "\n",
    "            return left + mid + right\n",
    "\n",
    "        return sortArray2(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "\n",
    "        if len(nums) == 0:\n",
    "            return nums\n",
    "        \n",
    "        def quicksort(tmp_list):\n",
    "            if len(tmp_list) <= 1:\n",
    "                return tmp_list\n",
    "            \n",
    "            pos = random.randint(0, len(tmp_list)-1)\n",
    "            val = tmp_list[pos]\n",
    "\n",
    "            left = []\n",
    "            right = []\n",
    "            eq = []\n",
    "\n",
    "            for vv in tmp_list:\n",
    "                if vv < val:\n",
    "                    left.append(vv)\n",
    "                elif vv > val:\n",
    "                    right.append(vv)\n",
    "                else:\n",
    "                    eq.append(vv)\n",
    "            \n",
    "            return quicksort(left) + eq + quicksort(right)\n",
    "        \n",
    "        return quicksort(nums)\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        \n",
    "        A=5*10**4\n",
    "        M=0\n",
    "        for i in range(len(nums)):\n",
    "            nums[i]+=A\n",
    "            M=max(nums[i],M)\n",
    "        N=10\n",
    "        c=1\n",
    "        while M!=0:\n",
    "            dic=dict()\n",
    "            for i in nums:\n",
    "                s=dic.get(i%(N*c)//c,[])\n",
    "                s.append(i)\n",
    "                dic[i%(N*c)//c]=s\n",
    "            nums=[]\n",
    "            for i in range(N):\n",
    "                nums.extend(dic.get(i,[]))\n",
    "            M=M//N\n",
    "            c*=N\n",
    "        for i in range(len(nums)):\n",
    "            nums[i]-=A\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        \n",
    "        A=5*10**4\n",
    "        M=0\n",
    "        for i in range(len(nums)):\n",
    "            nums[i]+=A\n",
    "            M=max(nums[i],M)\n",
    "        N=1000\n",
    "        c=1\n",
    "        while M!=0:\n",
    "            dic=dict()\n",
    "            for i in nums:\n",
    "                s=dic.get(i%(N*c)//c,[])\n",
    "                s.append(i)\n",
    "                dic[i%(N*c)//c]=s\n",
    "            nums=[]\n",
    "            for i in range(N):\n",
    "                nums.extend(dic.get(i,[]))\n",
    "            M=M//N\n",
    "            c*=N\n",
    "        for i in range(len(nums)):\n",
    "            nums[i]-=A\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        N=11\n",
    "        A=5*10**4\n",
    "        M=0\n",
    "        for i in range(len(nums)):\n",
    "            nums[i]+=A\n",
    "            M=max(nums[i],M)\n",
    "        c=1\n",
    "        while M!=0:\n",
    "            dic=dict()\n",
    "            for i in nums:\n",
    "                s=dic.get(i%(N*c)//c,[])\n",
    "                s.append(i)\n",
    "                dic[i%(N*c)//c]=s\n",
    "            nums=[]\n",
    "            for i in range(N):\n",
    "                nums.extend(dic.get(i,[]))\n",
    "            M=M//N\n",
    "            c*=N\n",
    "        for i in range(len(nums)):\n",
    "            nums[i]-=A\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        \n",
    "        A=5*10**4\n",
    "        M=0\n",
    "        for i in range(len(nums)):\n",
    "            nums[i]+=A\n",
    "            M=max(nums[i],M)\n",
    "        N=int(sqrt(M))\n",
    "        c=1\n",
    "        while M!=0:\n",
    "            dic=dict()\n",
    "            for i in nums:\n",
    "                s=dic.get(i%(N*c)//c,[])\n",
    "                s.append(i)\n",
    "                dic[i%(N*c)//c]=s\n",
    "            nums=[]\n",
    "            for i in range(N):\n",
    "                nums.extend(dic.get(i,[]))\n",
    "            M=M//N\n",
    "            c*=N\n",
    "        for i in range(len(nums)):\n",
    "            nums[i]-=A\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import random\n",
    "class Solution:\n",
    "    def sortArray(self, arr: List[int]) -> List[int]:\n",
    "      \n",
    "        if len(arr) <= 1:\n",
    "            return arr\n",
    " \n",
    "        pivot_index = random.randint(0, len(arr) - 1)\n",
    "        pivot = arr[pivot_index]\n",
    "        # less = [x for x in arr if x < pivot]\n",
    "        # equal = [x for x in arr if x == pivot]\n",
    "        # greater = [x for x in arr if x > pivot]\n",
    "        less = []\n",
    "        equal = []\n",
    "        greater = []\n",
    "        for x in arr:\n",
    "            if x < pivot:\n",
    "                less.append(x)\n",
    "            elif x == pivot:\n",
    "                equal.append(x)\n",
    "            else:\n",
    "                greater.append(x)\n",
    "\n",
    "        return self.sortArray(less) + equal + self.sortArray(greater)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    temp = []\n",
    "    mun = []\n",
    "    cnt = 0\n",
    "    \n",
    "    @staticmethod\n",
    "    def indexprint(cnt):\n",
    "        pass\n",
    "        # print(' '*cnt,end='')\n",
    "\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        for _ in range(len(nums)):\n",
    "            Solution.temp.append(0)\n",
    "        lo,hi = 0, len(nums)-1\n",
    "        # Solution.mun = nums\n",
    "        Solution.sort( nums,lo,hi )\n",
    "        # return Solution.mun\n",
    "        return nums \n",
    "        \n",
    "    @staticmethod\n",
    "    def sort(nums, lo, hi):\n",
    "        Solution.cnt = Solution.cnt + 1\n",
    "        if lo == hi:\n",
    "            Solution.indexprint(Solution.cnt)\n",
    "            print(lo,hi)\n",
    "            return\n",
    "        mid = lo + (hi-lo)//2\n",
    "        Solution.sort( nums, lo, mid )\n",
    "        Solution.sort( nums, mid+1, hi ) #少了个+1就成了无限递归了\n",
    "        Solution.merge( nums, lo, mid, hi )\n",
    "        Solution.cnt = Solution.cnt - 1\n",
    "\n",
    "    @staticmethod\n",
    "    def merge( nums, lo, mid, hi ):\n",
    "        for i in range(lo,hi+1):\n",
    "            Solution.temp[i] = nums[i]\n",
    "        \n",
    "        i,j = lo, mid+1\n",
    "        for p in range(lo,hi+1): #这儿要变！\n",
    "            if i == mid+1:\n",
    "                nums[p] = Solution.temp[j]\n",
    "                j += 1\n",
    "            elif j == hi + 1:\n",
    "                nums[p] = Solution.temp[i]\n",
    "                i+=1\n",
    "            elif Solution.temp[i]<Solution.temp[j]:\n",
    "                nums[p] = Solution.temp[i] #静态变量好难用啊，动不动就忘写了\n",
    "                i+=1 #索引值增加的语句会忘\n",
    "            else:\n",
    "                nums[p] = Solution.temp[j]\n",
    "                j+=1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        \n",
    "        A=5*10**4\n",
    "        M=0\n",
    "        for i in range(len(nums)):\n",
    "            nums[i]+=A\n",
    "            M=max(nums[i],M)\n",
    "        N=int(sqrt(M))\n",
    "        c=1\n",
    "        while M!=0:\n",
    "            dic=dict()\n",
    "            for i in nums:\n",
    "                s=dic.get(i%(N*c)//c,[])\n",
    "                s.append(i)\n",
    "                dic[i%(N*c)//c]=s\n",
    "            nums=[]\n",
    "            for i in range(N):\n",
    "                nums.extend(dic.get(i,[]))\n",
    "            M=M//N\n",
    "            c*=N\n",
    "        for i in range(len(nums)):\n",
    "            nums[i]-=A\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 桶排序\n",
    "class Solution:\n",
    "    def sortArray(self, nums):\n",
    "        def offset(li,b):\n",
    "            return [num+b for num in li]\n",
    "        max_num=100000\n",
    "        b=50000\n",
    "        nums=offset(nums,b)\n",
    "        m,n=1000,max_num//1000\n",
    "        buckets=[[] for _ in range(m)]\n",
    "        for num in nums:\n",
    "            k=min(num//n,m-1)\n",
    "            buckets[k].append(num)\n",
    "            j=len(buckets[k])-2\n",
    "            while j>=0 and buckets[k][j]>num:\n",
    "                buckets[k][j+1]=buckets[k][j]\n",
    "                j-=1\n",
    "            buckets[k][j+1]=num\n",
    "        nums.clear()\n",
    "        for i in range(m):\n",
    "            nums.extend(buckets[i])\n",
    "        nums=offset(nums,-b)\n",
    "        return nums\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        self.quicksort(nums,0,len(nums)-1)\n",
    "        return nums\n",
    "    def pickup(self,nums,start,end):\n",
    "        mid=start+(end-start)>>1\n",
    "        ns,nm,ne=nums[start],nums[mid],nums[end]\n",
    "        if ns<=nm<=ne or ne<=nm<ns:\n",
    "            return mid\n",
    "        elif  nm<=ns<=ne or ne<=ns<nm:\n",
    "            return start\n",
    "        else:\n",
    "            return end\n",
    "    def pickup1(self,nums,start,end):\n",
    "        mid=start+(end-start)>>1\n",
    "        if nums[start]>nums[mid]:\n",
    "            if nums[mid]>nums[end]:\n",
    "                return mid\n",
    "            elif nums[end]>nums[start]:\n",
    "                return start\n",
    "            else:\n",
    "                return end\n",
    "        else:\n",
    "            if nums[start]>nums[end]:\n",
    "                return start\n",
    "            elif nums[end]>nums[mid]:\n",
    "                return mid\n",
    "            else:\n",
    "                return end\n",
    "    def quicksort(self,nums,start,end):\n",
    "        if end<=start:\n",
    "            return\n",
    "\n",
    "        #pivot=random.randint(start,end)\n",
    "        pivot=self.pickup(nums,start,end)\n",
    "        tar=nums[pivot]\n",
    "        nums[pivot],nums[start]=nums[start],nums[pivot]\n",
    "        lp=start+1\n",
    "        rp=end+1\n",
    "        mp=lp\n",
    "        while mp<rp:\n",
    "            if nums[mp]<tar:\n",
    "                nums[mp],nums[lp]=nums[lp],nums[mp]\n",
    "                lp+=1\n",
    "                mp+=1\n",
    "            elif nums[mp]>tar:\n",
    "                nums[rp-1],nums[mp]=nums[mp],nums[rp-1]\n",
    "                rp-=1\n",
    "            else:\n",
    "                mp+=1\n",
    "        nums[start],nums[lp-1]=nums[lp-1],nums[start]\n",
    "        self.quicksort(nums,start,lp-2)\n",
    "        self.quicksort(nums,rp,end)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import random\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def sortArray(self, nums) :\n",
    "        def f(l, r,nums):\n",
    "            if l >= r:\n",
    "                return nums\n",
    "            index = random.randint(l,r)\n",
    "            nums[l], nums[index] = nums[index], nums[l]\n",
    "            middle_value = nums[l]\n",
    "            lo, hi = l, r\n",
    "            while hi > lo:\n",
    "                while hi > lo and nums[hi] >= middle_value:\n",
    "                    hi -= 1\n",
    "                nums[lo], nums[hi] = nums[hi], nums[lo]\n",
    "                while hi>lo and nums[lo]<=middle_value:\n",
    "                    lo+=1\n",
    "                nums[lo], nums[hi] = nums[hi], nums[lo]\n",
    "            f(l,lo-1,nums)\n",
    "            f(lo+1,r,nums)\n",
    "            return nums\n",
    "        num_dict = Counter(nums)\n",
    "        num_list = f(0,len(num_dict.keys())-1,list(num_dict.keys()))\n",
    "        index = 0\n",
    "        for num in num_list:\n",
    "            for _ in range(num_dict[num]):\n",
    "                nums[index]=num\n",
    "                index+=1\n",
    "        return nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        dic = {}\n",
    "        for i in nums:\n",
    "            dic[i] = dic.get(i,0) + 1\n",
    "        s = sorted(dic)\n",
    "        ind = 0\n",
    "        for x in s:\n",
    "            for y in range(dic[x]):\n",
    "                nums[ind] = x\n",
    "                ind += 1\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        if len(Counter(nums)) == 1:\n",
    "            return nums\n",
    "        if len(nums) > 1000 and len(Counter(nums[1:])) == 1:\n",
    "            return nums[1:] + [nums[0]]\n",
    "        def findmid(arr, left, right):\n",
    "            pivit = arr[left]\n",
    "            while left < right:\n",
    "                while left < right and arr[right] >= pivit:\n",
    "                    right -= 1\n",
    "                arr[left] = arr[right]\n",
    "                while left < right and arr[left] <= pivit:\n",
    "                    left += 1\n",
    "                arr[right] = arr[left]\n",
    "            arr[left] = pivit\n",
    "            return left\n",
    "        def random_pivot(arr, left, right):\n",
    "            pivit_index = randint(left, right)\n",
    "            arr[left], arr[pivit_index] = arr[pivit_index], arr[left]\n",
    "            return findmid(arr, left, right)\n",
    "        def quicksort(arr, left, right):\n",
    "            if left > right:\n",
    "                return\n",
    "            mid = random_pivot(arr, left, right)\n",
    "            quicksort(arr, left, mid-1)\n",
    "            quicksort(arr, mid+1, right)\n",
    "        quicksort(nums, 0, len(nums)-1)\n",
    "        return nums\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        min_num = min(nums)\n",
    "        nums = [num-min_num for num in nums]\n",
    "        from math import log\n",
    "        offset = 1\n",
    "        BASE = 10\n",
    "        help = [0 for i in range(len(nums))]\n",
    "        digit = int(log(max(1, max(nums)), 10))+1\n",
    "        for _ in range(digit):\n",
    "            pre = [0 for i in range(BASE)]\n",
    "            for j in range(len(nums)):\n",
    "                pre[(nums[j]//offset)%BASE] += 1\n",
    "            for j in range(1, len(pre)):\n",
    "                pre[j] += pre[j-1]\n",
    "            # print(pre)\n",
    "            for j in range(len(nums)-1, -1, -1):\n",
    "                # print('pre[(nums[j]//offset)%BASE]-1', pre[(nums[j]//offset)%BASE]-1, 'nums[j]', nums[j])\n",
    "                help[pre[(nums[j]//offset)%BASE]-1] = nums[j]\n",
    "                pre[(nums[j]//offset)%BASE] -= 1\n",
    "            \n",
    "            nums = help[:]\n",
    "            offset *= BASE\n",
    "            # print(nums)\n",
    "        return [num+min_num for num in nums]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        min_num = min(nums)\n",
    "        nums = [num-min_num for num in nums]\n",
    "        from math import log\n",
    "        offset = 1\n",
    "        BASE = 100\n",
    "        help = [0 for i in range(len(nums))]\n",
    "        digit = int(log(max(1, max(nums)), 10))+1\n",
    "        for _ in range(digit):\n",
    "            pre = [0 for i in range(BASE)]\n",
    "            for j in range(len(nums)):\n",
    "                pre[(nums[j]//offset)%BASE] += 1\n",
    "            for j in range(1, len(pre)):\n",
    "                pre[j] += pre[j-1]\n",
    "            for j in range(len(nums)-1, -1, -1):\n",
    "                help[pre[(nums[j]//offset)%BASE]-1] = nums[j]\n",
    "                pre[(nums[j]//offset)%BASE] -= 1\n",
    "            nums = help[:]\n",
    "            offset *= BASE\n",
    "        return [num+min_num for num in nums]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        min_num = min(nums)\n",
    "        nums = [num-min_num for num in nums]\n",
    "        from math import log\n",
    "        offset = 1\n",
    "        BASE = 1024\n",
    "        help = [0 for i in range(len(nums))]\n",
    "        digit = int(log(max(1, max(nums)), 10))+1\n",
    "        for _ in range(digit):\n",
    "            pre = [0 for i in range(BASE)]\n",
    "            for j in range(len(nums)):\n",
    "                pre[(nums[j]//offset)%BASE] += 1\n",
    "            for j in range(1, len(pre)):\n",
    "                pre[j] += pre[j-1]\n",
    "            for j in range(len(nums)-1, -1, -1):\n",
    "                help[pre[(nums[j]//offset)%BASE]-1] = nums[j]\n",
    "                pre[(nums[j]//offset)%BASE] -= 1\n",
    "            nums = help[:]\n",
    "            offset *= BASE\n",
    "        return [num+min_num for num in nums]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        min_num = min(nums)\n",
    "        nums = [num-min_num for num in nums]\n",
    "        from math import log\n",
    "        offset = 1\n",
    "        BASE = 1000\n",
    "        help = [0 for i in range(len(nums))]\n",
    "        digit = int(log(max(1, max(nums)), 10))+1\n",
    "        for _ in range(digit):\n",
    "            pre = [0 for i in range(BASE)]\n",
    "            for j in range(len(nums)):\n",
    "                pre[(nums[j]//offset)%BASE] += 1\n",
    "            for j in range(1, len(pre)):\n",
    "                pre[j] += pre[j-1]\n",
    "            for j in range(len(nums)-1, -1, -1):\n",
    "                help[pre[(nums[j]//offset)%BASE]-1] = nums[j]\n",
    "                pre[(nums[j]//offset)%BASE] -= 1\n",
    "            nums = help[:]\n",
    "            offset *= BASE\n",
    "        return [num+min_num for num in nums]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        # 筒排序\n",
    "        minnum = min(nums)\n",
    "        maxnum = max(nums)\n",
    "        if minnum == maxnum:\n",
    "            return nums\n",
    "        n = len(nums)\n",
    "        l = maxnum - minnum +1\n",
    "        bsize = math.ceil(l / n)\n",
    "        #bcnt=n\n",
    "        bucket=[[] for _ in range(n)]\n",
    "        \n",
    "        for num in nums:\n",
    "            more=num-minnum\n",
    "            i=more//bsize\n",
    "            bucket[i].append(num)\n",
    "        ans=[]\n",
    "        for b in bucket:\n",
    "            if len(b)==1:\n",
    "                ans+=b \n",
    "            elif len(b)>1:\n",
    "                ans+=self.sortArray(b)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        min_num = min(nums)\n",
    "        max_num = max(nums)\n",
    "        # 桶的大小\n",
    "        bucket_range = (max_num-min_num) / len(nums)\n",
    "        if bucket_range==0:\n",
    "            return nums\n",
    "        # 桶数组\n",
    "        count_list = [ [] for i in range(len(nums) + 1)]\n",
    "        # 向桶数组填数\n",
    "        for i in nums:\n",
    "            count_list[int((i-min_num)//bucket_range)].append(i)\n",
    "        nums.clear()\n",
    "        # 回填，这里桶内部排序直接调用了sorted\n",
    "        for i in count_list:\n",
    "            for j in sorted(i):\n",
    "                nums.append(j)\n",
    "        return nums\n",
    "\n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        min_num = min(nums)\n",
    "        nums = [num-min_num for num in nums]\n",
    "        from math import log\n",
    "        offset = 1\n",
    "        BASE = 5000\n",
    "        help = [0 for i in range(len(nums))]\n",
    "        digit = int(log(max(1, max(nums)), 10))+1\n",
    "        for _ in range(digit):\n",
    "            pre = [0 for i in range(BASE)]\n",
    "            for j in range(len(nums)):\n",
    "                pre[(nums[j]//offset)%BASE] += 1\n",
    "            for j in range(1, len(pre)):\n",
    "                pre[j] += pre[j-1]\n",
    "            for j in range(len(nums)-1, -1, -1):\n",
    "                help[pre[(nums[j]//offset)%BASE]-1] = nums[j]\n",
    "                pre[(nums[j]//offset)%BASE] -= 1\n",
    "            nums = help[:]\n",
    "            offset *= BASE\n",
    "        return [num+min_num for num in nums]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        # 选择排序，超时\n",
    "        # for i in range(len(nums) - 1):\n",
    "        #     min_i  = i\n",
    "        #     for j in range(i + 1, len(nums)):\n",
    "        #         if nums[j] < nums[min_i]:\n",
    "        #             min_i = j\n",
    "        #     if min_i != i:\n",
    "        #         nums[i], nums[min_i] = nums[min_i], nums[i]\n",
    "        # return nums\n",
    "\n",
    "        # 插入排序，超时\n",
    "        # for i in range(1, len(nums)):\n",
    "        #     temp = nums[i]\n",
    "        #     j = i\n",
    "        #     while j > 0 and nums[j - 1] > temp:\n",
    "        #         nums[j] = nums[j - 1]\n",
    "        #         j -= 1\n",
    "        #     nums[j] = temp\n",
    "        # return nums\n",
    "\n",
    "        # 希尔排序，通过\n",
    "        # size = len(nums)\n",
    "        # gap = size // 2\n",
    "\n",
    "        # while gap > 0:\n",
    "        #     for i in range(gap, size):\n",
    "        #         temp = nums[i]\n",
    "        #         j = i\n",
    "        #         while j > 0 and nums[j - gap] > temp:\n",
    "        #             nums[j] = nums[j - gap]\n",
    "        #             j -= gap\n",
    "        #         nums[j] = temp\n",
    "        #     gap = gap // 2\n",
    "        # return nums\n",
    "\n",
    "    #     # 归并排序，通过\n",
    "    #     nums = self.mergeSort(nums)\n",
    "    #     return nums\n",
    "    \n",
    "    # def merge(self, left_nums, right_nums):\n",
    "    #     nums = []\n",
    "    #     left_i = 0\n",
    "    #     right_i = 0\n",
    "    #     while left_i < len(left_nums) and right_i < len(right_nums):\n",
    "    #         if left_nums[left_i] < right_nums[right_i]:\n",
    "    #             nums.append(left_nums[left_i])\n",
    "    #             left_i += 1\n",
    "    #         else:\n",
    "    #             nums.append(right_nums[right_i])\n",
    "    #             right_i += 1\n",
    "        \n",
    "    #     while left_i < len(left_nums):\n",
    "    #         nums.append(left_nums[left_i])\n",
    "    #         left_i += 1\n",
    "        \n",
    "    #     while right_i < len(right_nums):\n",
    "    #         nums.append(right_nums[right_i])\n",
    "    #         right_i += 1\n",
    "\n",
    "    #     return nums\n",
    "    \n",
    "    # def mergeSort(self, nums):\n",
    "    #     if len(nums) == 1:\n",
    "    #         return nums\n",
    "        \n",
    "    #     mid = len(nums) // 2\n",
    "    #     left_nums = self.mergeSort(nums[:mid])\n",
    "    #     right_nums = self.mergeSort(nums[mid:])\n",
    "    #     return self.merge(left_nums, right_nums)\n",
    "\n",
    "    #     # 快速排序，超时\n",
    "    #     return self.quickSort(nums, 0, len(nums) - 1)\n",
    "\n",
    "    # def randomPartition(self, nums, low, high):\n",
    "    #     import random\n",
    "    #     i = random.randint(low, high)\n",
    "    #     nums[i], nums[low] = nums[low], nums[i]\n",
    "    #     return self.partition(nums, low, high)\n",
    "    \n",
    "    # def partition(self, nums, low, high):\n",
    "    #     pivot = nums[low]\n",
    "    #     i, j = low, high\n",
    "        \n",
    "    #     while i < j:\n",
    "    #         while i < j and nums[j] >= pivot:\n",
    "    #             j -= 1\n",
    "    #         while i < j and nums[i] <= pivot:\n",
    "    #             i += 1\n",
    "    #         nums[i], nums[j] = nums[j], nums[i]\n",
    "    #     nums[low], nums[i] = nums[i], nums[low]\n",
    "\n",
    "    #     return i\n",
    "\n",
    "    # def quickSort(self, nums, low, high):\n",
    "    #     if low < high:\n",
    "    #         pivot_i = self.randomPartition(nums, low, high)\n",
    "    #         self.quickSort(nums, low, pivot_i - 1)\n",
    "    #         self.quickSort(nums, pivot_i + 1, high)\n",
    "    #     return nums\n",
    "        \n",
    "\n",
    "    #     # 堆排序，通过\n",
    "    #     return self.maxHeapSort(nums)\n",
    "\n",
    "    # # 调整为大顶堆\n",
    "    # def heapify(self, arr, index, end):\n",
    "    #     left = index * 2 + 1\n",
    "    #     right = left + 1\n",
    "\n",
    "    #     while left <= end:\n",
    "    #         max_index = index\n",
    "    #         if arr[left] > arr[max_index]:\n",
    "    #             max_index = left\n",
    "    #         if right <= end and arr[right] > arr[max_index]:\n",
    "    #             max_index = right\n",
    "    #         if index == max_index:\n",
    "    #             break\n",
    "    #         arr[index], arr[max_index] = arr[max_index], arr[index]\n",
    "    #         index = max_index\n",
    "    #         left = index * 2 + 1\n",
    "    #         right = left + 1\n",
    "    \n",
    "    # # 初始化大顶堆\n",
    "    # def buildMaxHeap(self, arr):\n",
    "    #     size = len(arr)\n",
    "    #     for i in range((size - 2) // 2, -1, -1):\n",
    "    #         self.heapify(arr, i, size - 1)\n",
    "    #     return arr\n",
    "    \n",
    "    # def maxHeapSort(self, arr):\n",
    "    #     self.buildMaxHeap(arr)\n",
    "    #     size = len(arr)\n",
    "    #     for i in range(size):\n",
    "    #         arr[0], arr[size - i - 1] = arr[size - i - 1], arr[0]\n",
    "    #         self.heapify(arr, 0, size - i - 2)\n",
    "    #     return arr\n",
    "\n",
    "    #     # 计数排序，通过\n",
    "    #     return self.countingSort(nums)\n",
    "\n",
    "    # def countingSort(self, nums):\n",
    "    #     nums_min, nums_max = min(nums), max(nums)\n",
    "    #     size = nums_max - nums_min + 1\n",
    "    #     counts = [0 for _ in range(size)]\n",
    "\n",
    "    #     for num in nums:\n",
    "    #         counts[num - nums_min] += 1\n",
    "        \n",
    "    #     for i in range(1, size):\n",
    "    #         counts[i] += counts[i - 1]\n",
    "        \n",
    "    #     res = [0 for _ in range(len(nums))]\n",
    "\n",
    "    #     for i in range(len(nums) - 1, -1, -1):\n",
    "    #         counts[nums[i] - nums_min] -= 1\n",
    "    #         res[counts[nums[i] - nums_min]] = nums[i]\n",
    "        \n",
    "    #     return res\n",
    "\n",
    "        # 桶排序\n",
    "        return self.bucketSort(nums, bucket_size=1)\n",
    "\n",
    "    def bucketSort(self, nums, bucket_size=5):\n",
    "        nums_min, nums_max = min(nums), max(nums)\n",
    "        bucket_count = (nums_max - nums_min) // bucket_size + 1\n",
    "        buckets = [[] for _ in range(bucket_count)]\n",
    "\n",
    "        for num in nums:\n",
    "            buckets[(num - nums_min) // bucket_size].append(num)\n",
    "        \n",
    "        res = []\n",
    "        \n",
    "        # 对每个桶执行基本排序算法，这里使用插入排序\n",
    "        for bucket in buckets:\n",
    "            for i in range(1, len(bucket)):\n",
    "                temp = bucket[i]\n",
    "                j = i\n",
    "                while j > 0 and bucket[j - 1] > temp:\n",
    "                    bucket[j] = bucket[j - 1]\n",
    "                    j -= 1\n",
    "                bucket[j] = temp\n",
    "            res.extend(bucket)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 选择剩下元素中最小的元素，依次往前面排\n",
    "    # \\U0001d442(\\U0001d45b2)\n",
    "    def selectionSort(self,nums):\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            # 寻找i位置的目标元素\n",
    "            min=i\n",
    "            # 从余下的元素中找到最小元素\n",
    "            for j in range(i,n):\n",
    "                if nums[j]<nums[min]:\n",
    "                    min=j\n",
    "            # 交换\n",
    "            nums[i],nums[min]=nums[min],nums[i]\n",
    "\n",
    "    # 冒泡排序和选择排序的外层逻辑类似\n",
    "    # 都是选择剩下元素中最小的元素，依次往前面排\n",
    "    # 不过里面找的逻辑不一样，选择排序直接遍历查找\n",
    "    # 而冒泡排序选择两两比较，冒泡的方式\n",
    "    def bubbleSort(self,nums):\n",
    "        n=len(nums)\n",
    "        # 最后一个就不用冒了\n",
    "        for i in range(0,n-1):\n",
    "            # 从[n-1,i]，把最小的冒到i的位置\n",
    "            for j in range(n-1,i,-1):\n",
    "                if nums[j]<nums[j-1]:\n",
    "                    nums[j],nums[j-1]=nums[j-1],nums[j]\n",
    "    # 插入排序和打牌类似\n",
    "    def insertionSort(self,nums):\n",
    "        n=len(nums)\n",
    "        for i in range(1,n):\n",
    "            # 操作[0,i]，[0,i-1]已经排序好，把i+1前插到[0,i-1]的指定位置\n",
    "            for j in range(i):\n",
    "                if nums[i]<nums[j]:\n",
    "                    # [j,i-1]后移1位，[j+1,i];\n",
    "                    # 然后把i插入j的位置\n",
    "                    nums[j+1:i+1],nums[j]=nums[j:i],nums[i]\n",
    "\n",
    "     # 计数排序，以空间换时间               \n",
    "    def countSort(self,nums):\n",
    "        valmin,valmax=min(nums),max(nums)\n",
    "        map={}\n",
    "        for i in nums:\n",
    "            if i in map.keys():\n",
    "                map[i]+=1\n",
    "            else:\n",
    "                map[i]=1\n",
    "        j=0\n",
    "        for i in range(valmin,valmax+1):\n",
    "            if i in map.keys():\n",
    "                length=map[i]\n",
    "                nums[j:j+length]=[i]*length\n",
    "                j+=length\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    def merge(self,nums,l,mid,r):\n",
    "        # [l,r]\n",
    "        # 左子数组区间 [l, mid]\n",
    "        # 右子数组区间 [mid + 1, r]\n",
    "        tmp = nums[l:r+1]\n",
    "        # 数组左半部分和右半部分\n",
    "        # 也就是查出[l,r]，然后平移l\n",
    "        left0,left1=0,mid-l\n",
    "        right0,right1=mid+1-l,r-l\n",
    "        i,j=left0,right0\n",
    "        # 对原来的数组进行操作\n",
    "        for k in range(l,r+1):\n",
    "            # 分别是左、右部分元素遍历完成的情况\n",
    "            if i>left1:\n",
    "                nums[k]=tmp[j]\n",
    "                j+=1\n",
    "            elif j>right1:\n",
    "                nums[k]=tmp[i]\n",
    "                i+=1\n",
    "            # 不然，小的先进去\n",
    "            elif tmp[i]<tmp[j]:\n",
    "                nums[k]=tmp[i]\n",
    "                i+=1\n",
    "            else:\n",
    "                nums[k]=tmp[j]\n",
    "                j+=1\n",
    "\n",
    "    # 排序[l,r]的元素\n",
    "    def mergeSort(self,nums,l,r):\n",
    "        # 一个元素肯定是有序的，也无法再分\n",
    "        # 最顶层是拆成了两个或是一个，然后进行操作\n",
    "        if l==r:return\n",
    "        mid=l+r>>1\n",
    "        # 分别排序左右部分\n",
    "        self.mergeSort(nums,l,mid)\n",
    "        self.mergeSort(nums,mid+1,r)\n",
    "        # 然后合并\n",
    "        # 最底层是两个元素的合并\n",
    "        self.merge(nums,l,mid,r)\n",
    "\n",
    "\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        flag=5\n",
    "\n",
    "        if flag==1:\n",
    "            self.selectionSort(nums)\n",
    "        if flag==2:\n",
    "            self.bubbleSort(nums)\n",
    "        if flag==3:\n",
    "            self.insertionSort(nums)\n",
    "        if flag==4:\n",
    "            self.mergeSort(nums,0,len(nums)-1)\n",
    "        if flag==5:\n",
    "            self.countSort(nums)\n",
    "\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 选择剩下元素中最小的元素，依次往前面排\n",
    "    # \\U0001d442(\\U0001d45b2)\n",
    "    def selectionSort(self,nums):\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            # 寻找i位置的目标元素\n",
    "            min=i\n",
    "            # 从余下的元素中找到最小元素\n",
    "            for j in range(i,n):\n",
    "                if nums[j]<nums[min]:\n",
    "                    min=j\n",
    "            # 交换\n",
    "            nums[i],nums[min]=nums[min],nums[i]\n",
    "\n",
    "    # 冒泡排序和选择排序的外层逻辑类似\n",
    "    # 都是选择剩下元素中最小的元素，依次往前面排\n",
    "    # 不过里面找的逻辑不一样，选择排序直接遍历查找\n",
    "    # 而冒泡排序选择两两比较，冒泡的方式\n",
    "    def bubbleSort(self,nums):\n",
    "        n=len(nums)\n",
    "        # 最后一个就不用冒了\n",
    "        for i in range(0,n-1):\n",
    "            # 从[n-1,i]，把最小的冒到i的位置\n",
    "            for j in range(n-1,i,-1):\n",
    "                if nums[j]<nums[j-1]:\n",
    "                    nums[j],nums[j-1]=nums[j-1],nums[j]\n",
    "    # 插入排序和打牌类似\n",
    "    def insertionSort(self,nums):\n",
    "        n=len(nums)\n",
    "        for i in range(1,n):\n",
    "            # 操作[0,i]，[0,i-1]已经排序好，把i+1前插到[0,i-1]的指定位置\n",
    "            for j in range(i):\n",
    "                if nums[i]<nums[j]:\n",
    "                    # [j,i-1]后移1位，[j+1,i];\n",
    "                    # 然后把i插入j的位置\n",
    "                    nums[j+1:i+1],nums[j]=nums[j:i],nums[i]\n",
    "                    \n",
    "    def countSort(self,nums):\n",
    "        valmin,valmax=min(nums),max(nums)\n",
    "        map={}\n",
    "        for i in nums:\n",
    "            if i in map.keys():\n",
    "                map[i]+=1\n",
    "            else:\n",
    "                map[i]=1\n",
    "        j=0\n",
    "        for i in range(valmin,valmax+1):\n",
    "            if i in map.keys():\n",
    "                length=map[i]\n",
    "                nums[j:j+length]=[i]*length\n",
    "                j+=length\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    def merge(self,nums,l,mid,r):\n",
    "        # [l,r]\n",
    "        # 左子数组区间 [l, mid]\n",
    "        # 右子数组区间 [mid + 1, r]\n",
    "        tmp = nums[l:r+1]\n",
    "        # 数组左半部分和右半部分\n",
    "        # 也就是查出[l,r]，然后平移l\n",
    "        left0,left1=0,mid-l\n",
    "        right0,right1=mid+1-l,r-l\n",
    "        i,j=left0,right0\n",
    "        # 对原来的数组进行操作\n",
    "        for k in range(l,r+1):\n",
    "            # 分别是左、右部分元素遍历完成的情况\n",
    "            if i>left1:\n",
    "                nums[k]=tmp[j]\n",
    "                j+=1\n",
    "            elif j>right1:\n",
    "                nums[k]=tmp[i]\n",
    "                i+=1\n",
    "            # 不然，小的先进去\n",
    "            elif tmp[i]<tmp[j]:\n",
    "                nums[k]=tmp[i]\n",
    "                i+=1\n",
    "            else:\n",
    "                nums[k]=tmp[j]\n",
    "                j+=1\n",
    "\n",
    "    # 排序[l,r]的元素\n",
    "    def mergeSort(self,nums,l,r):\n",
    "        # 一个元素肯定是有序的，也无法再分\n",
    "        # 最顶层是拆成了两个或是一个，然后进行操作\n",
    "        if l==r:return\n",
    "        mid=l+r>>1\n",
    "        # 分别排序左右部分\n",
    "        self.mergeSort(nums,l,mid)\n",
    "        self.mergeSort(nums,mid+1,r)\n",
    "        # 然后合并\n",
    "        # 最底层是两个元素的合并\n",
    "        self.merge(nums,l,mid,r)\n",
    "\n",
    "\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        flag=5\n",
    "\n",
    "        if flag==1:\n",
    "            self.selectionSort(nums)\n",
    "        if flag==2:\n",
    "            self.bubbleSort(nums)\n",
    "        if flag==3:\n",
    "            self.insertionSort(nums)\n",
    "        if flag==4:\n",
    "            self.mergeSort(nums,0,len(nums)-1)\n",
    "        if flag==5:\n",
    "            self.countSort(nums)\n",
    "\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        def RadixSorted(nums,radix):\n",
    "            if maxValue//radix == 0:\n",
    "                return nums\n",
    "            res = []\n",
    "            arr = []\n",
    "            Buckets = [[] for _ in range(10)]\n",
    "            for num in nums:\n",
    "                Buckets[num//radix%10].append(num)\n",
    "            for Bucket in Buckets:\n",
    "                for num in Bucket:\n",
    "                    if num // radix == 0:\n",
    "                        res.append(num)\n",
    "                    else:\n",
    "                        arr.append(num)\n",
    "\n",
    "            return res + RadixSorted(arr,radix*10)\n",
    "\n",
    "        r = len(nums) - 1\n",
    "        l = 0\n",
    "        while l < r:\n",
    "            while l < r and nums[l] < 0:\n",
    "                l += 1\n",
    "            while l < r and nums[r] >= 0:\n",
    "                r -= 1\n",
    "            nums[l], nums[r] = nums[r], nums[l]\n",
    "        global maxValue\n",
    "        res1, res2, maxValue = [], [], 0\n",
    "        PositiveNums = nums[r:]\n",
    "        NegativeNums = nums[:l]\n",
    "        if PositiveNums:\n",
    "            maxValue = max(PositiveNums)\n",
    "            res1 = RadixSorted(PositiveNums,1)\n",
    "        if NegativeNums:\n",
    "            maxValue = min(NegativeNums)\n",
    "            res2 = RadixSorted(NegativeNums,-1)\n",
    "        return res2[::-1] + res1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        mini, maxi = min(nums), max(nums)\n",
    "        dic = {k:0 for k in range(mini, maxi + 1)}\n",
    "        res = []\n",
    "        for n in nums:\n",
    "            dic[n] += 1\n",
    "        for num, count in dic.items():\n",
    "            if count > 0:\n",
    "                res += [num] * count\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 选择剩下元素中最小的元素，依次往前面排\n",
    "    # \\U0001d442(\\U0001d45b2)\n",
    "    def selectionSort(self,nums):\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            # 寻找i位置的目标元素\n",
    "            min=i\n",
    "            # 从余下的元素中找到最小元素\n",
    "            for j in range(i,n):\n",
    "                if nums[j]<nums[min]:\n",
    "                    min=j\n",
    "            # 交换\n",
    "            nums[i],nums[min]=nums[min],nums[i]\n",
    "\n",
    "    # 冒泡排序和选择排序的外层逻辑类似\n",
    "    # 都是选择剩下元素中最小的元素，依次往前面排\n",
    "    # 不过里面找的逻辑不一样，选择排序直接遍历查找\n",
    "    # 而冒泡排序选择两两比较，冒泡的方式\n",
    "    def bubbleSort(self,nums):\n",
    "        n=len(nums)\n",
    "        # 最后一个就不用冒了\n",
    "        for i in range(0,n-1):\n",
    "            # 从[n-1,i]，把最小的冒到i的位置\n",
    "            for j in range(n-1,i,-1):\n",
    "                if nums[j]<nums[j-1]:\n",
    "                    nums[j],nums[j-1]=nums[j-1],nums[j]\n",
    "    # 插入排序和打牌类似\n",
    "    def insertionSort(self,nums):\n",
    "        n=len(nums)\n",
    "        for i in range(1,n):\n",
    "            # 操作[0,i]，[0,i-1]已经排序好，把i+1前插到[0,i-1]的指定位置\n",
    "            for j in range(i):\n",
    "                if nums[i]<nums[j]:\n",
    "                    # [j,i-1]后移1位，[j+1,i];\n",
    "                    # 然后把i插入j的位置\n",
    "                    nums[j+1:i+1],nums[j]=nums[j:i],nums[i]\n",
    "\n",
    "     # 计数排序，以空间换时间               \n",
    "    def countSort(self,nums):\n",
    "        _min,_max=min(nums),max(nums)\n",
    "        map={}\n",
    "        for i in nums:\n",
    "            if i in map.keys():\n",
    "                map[i]+=1\n",
    "            else:\n",
    "                map[i]=1\n",
    "        j=0\n",
    "        for i in range(_min,_max+1):\n",
    "            if i in map.keys():\n",
    "                length=map[i]\n",
    "                nums[j:j+length]=[i]*length\n",
    "                j+=length\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    def merge(self,nums,l,mid,r):\n",
    "        # [l,r]\n",
    "        # 左子数组区间 [l, mid]\n",
    "        # 右子数组区间 [mid + 1, r]\n",
    "        tmp = nums[l:r+1]\n",
    "        # 数组左半部分和右半部分\n",
    "        # 也就是查出[l,r]，然后平移l\n",
    "        left0,left1=0,mid-l\n",
    "        right0,right1=mid+1-l,r-l\n",
    "        i,j=left0,right0\n",
    "        # 对原来的数组进行操作\n",
    "        for k in range(l,r+1):\n",
    "            # 分别是左、右部分元素遍历完成的情况\n",
    "            if i>left1:\n",
    "                nums[k]=tmp[j]\n",
    "                j+=1\n",
    "            elif j>right1:\n",
    "                nums[k]=tmp[i]\n",
    "                i+=1\n",
    "            # 不然，小的先进去\n",
    "            elif tmp[i]<tmp[j]:\n",
    "                nums[k]=tmp[i]\n",
    "                i+=1\n",
    "            else:\n",
    "                nums[k]=tmp[j]\n",
    "                j+=1\n",
    "\n",
    "    # 排序[l,r]的元素\n",
    "    def mergeSort(self,nums,l,r):\n",
    "        # 一个元素肯定是有序的，也无法再分\n",
    "        # 最顶层是拆成了两个或是一个，然后进行操作\n",
    "        if l==r:return\n",
    "        mid=l+r>>1\n",
    "        # 分别排序左右部分\n",
    "        self.mergeSort(nums,l,mid)\n",
    "        self.mergeSort(nums,mid+1,r)\n",
    "        # 然后合并\n",
    "        # 最底层是两个元素的合并\n",
    "        self.merge(nums,l,mid,r)\n",
    "\n",
    "    # 桶排序\n",
    "    def bucketSort(self,nums,bucketSize=10):\n",
    "        _min,_max=min(nums),max(nums)\n",
    "        # 桶的个数。地板除，说明不够一个，再加一\n",
    "        # 换个角度理解，值域[0,(_max-_min)//bucketSize],但是数组索引从左闭右开需要加1\n",
    "        bucketNum=(_max-_min)//bucketSize+1\n",
    "        buckets=[[] for _ in range(bucketNum)]\n",
    "        for i in nums:\n",
    "            buckets[ (i-_min)//bucketSize ].append(i)\n",
    "        left=0\n",
    "        for i in buckets:\n",
    "            i.sort()\n",
    "            nums[left:left+len(i)]=i[:]\n",
    "            left+=len(i)\n",
    "\n",
    "    # 基数排序就是重复使用计数排序，解决其数据分散时效率低的问题\n",
    "    # 个十百千……先是细粒度的比较，然后再粗粒度\n",
    "    # 不支持负数，要比较负数，先减去一个最小值\n",
    "    def radixSort(self,nums):\n",
    "        if not nums:return\n",
    "        _max,_min=max(nums),min(nums)\n",
    "        # 最大数的位数\n",
    "        maxLen=len(str(_max))\n",
    "        # 创建10个桶 0-9十个数字\n",
    "        bucketList=[[] for _ in range(10)]\n",
    "        div,mod=1,10\n",
    "        for i in range(maxLen):\n",
    "            # num%mod//div确定了某个位的值\n",
    "            # 例如num=12345\n",
    "            # 1、12345%10=5 5//1=5\n",
    "            # 2、12345%100=45 45//10=4\n",
    "            # 一个用于去前缀//  一个用于去后缀%\n",
    "            # 这里就是，按照某位的值，把num放入到某个桶中\n",
    "            for num in nums:\n",
    "                bucketList[num%mod//div].append(num)\n",
    "            div*=10\n",
    "            mod*=10\n",
    "\n",
    "            # 再把桶里的元素按顺序取出来\n",
    "            idx=0\n",
    "            for j in range(10):\n",
    "                for k in bucketList[j]:\n",
    "                    nums[idx]=k\n",
    "                    idx+=1\n",
    "                bucketList[j]=[]\n",
    "        return nums\n",
    "\n",
    "    def heapSort(self,arr):\n",
    "        def maxHeapify(arr, n, subroot):\n",
    "            # 最大索引，默认为subroot\n",
    "            maxIndex = subroot\n",
    "            # 左右子节点\n",
    "            left, right = 2 * subroot + 1, 2 * subroot + 2\n",
    "\n",
    "            # 更新最大索引，若是左右子节点存在则比较\n",
    "            if left < n and arr[left] > arr[subroot]: maxIndex = left\n",
    "            if right < n and arr[right] > arr[maxIndex]: maxIndex = right\n",
    "\n",
    "            # 说明subroot不是最大的，需要更新\n",
    "            if maxIndex != subroot:\n",
    "                arr[maxIndex], arr[subroot] = arr[subroot], arr[maxIndex]\n",
    "                # maxIndex子树受到了改动，需要更新\n",
    "                maxHeapify(arr, n, maxIndex)\n",
    "        n = len(arr)\n",
    "        # 最后一个有孩子的节点\n",
    "        # 某非根节点的下标为i，那么其父节点为(i-1)//2\n",
    "        last = (n - 1 - 1) // 2\n",
    "        # 从下到上，构建出一个大顶堆\n",
    "        for i in range(last, -1, -1):\n",
    "            maxHeapify(arr, n, i)\n",
    "\n",
    "        # arr[i:]存储着已经排序好的数\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            arr[i], arr[0] = arr[0], arr[i]\n",
    "            maxHeapify(arr, i, 0)\n",
    "\n",
    "\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        flag=5\n",
    "\n",
    "        if flag==1:\n",
    "            self.selectionSort(nums)\n",
    "        if flag==2:\n",
    "            self.bubbleSort(nums)\n",
    "        if flag==3:\n",
    "            self.insertionSort(nums)\n",
    "        if flag==4:\n",
    "            self.mergeSort(nums,0,len(nums)-1)\n",
    "        if flag==5:\n",
    "            self.countSort(nums)\n",
    "        if flag==6:\n",
    "            # 先做一个线性偏移，使其非负数\n",
    "            n,_min=len(nums),min(nums)\n",
    "            for i in range(n):nums[i]-=_min\n",
    "            self.radixSort(nums)\n",
    "            for i in range(n):nums[i]+=_min\n",
    "        if flag==7:\n",
    "            self.bucketSort(nums)\n",
    "        if flag==8:\n",
    "            self.heapSort(nums)\n",
    "\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        hashmap = Counter(nums)\n",
    "        offer = min(nums)\n",
    "        len_ = max(nums) - offer\n",
    "        countlist = [0] * (len_ + 1)\n",
    "        for key in hashmap:\n",
    "            countlist[key - offer] += hashmap[key]\n",
    "        newnums = []\n",
    "        # print(hashmap, countlist)\n",
    "        for ind, i in enumerate(countlist):\n",
    "            for _ in range(i):\n",
    "                newnums.append(ind + offer)\n",
    "        return newnums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        flag=True\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i]<nums[i-1]:\n",
    "                flag=False\n",
    "        if flag:\n",
    "            return nums\n",
    "        def patition(left,right):\n",
    "            if left>right:\n",
    "                return\n",
    "            t=quicksort(left,right)\n",
    "            patition(left,t-1)\n",
    "            patition(t+1,right)\n",
    "        \n",
    "        def quicksort(left,right):\n",
    "            t=random.randint(left,right)\n",
    "            nums[t],nums[left]=nums[left],nums[t]\n",
    "            t=nums[left]\n",
    "            l,r=left,right\n",
    "            while l<r:\n",
    "                # print(l,r,nums,nums[r],t)\n",
    "                while l<r and nums[r]>t:\n",
    "                    r-=1\n",
    "                nums[l]=nums[r]\n",
    "                while l<r and nums[l]<=t:\n",
    "                    l+=1\n",
    "                nums[r]=nums[l]\n",
    "            nums[l]=t\n",
    "            return l\n",
    "        \n",
    "        patition(0,len(nums)-1)\n",
    "\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        d = dict()\n",
    "        clean_d = dict()\n",
    "        for i in nums:\n",
    "            if i in d.keys():\n",
    "                d[i] += 1\n",
    "            else:\n",
    "                d[i] = 1\n",
    "        for k, v in d.items():\n",
    "            if d[k] > 1:\n",
    "                clean_d[k] = v\n",
    "        t_nums = list(set(nums))\n",
    "        def swap(nums, a, b):\n",
    "            tmp = nums[b]\n",
    "            nums[b] = nums[a]\n",
    "            nums[a] = tmp\n",
    "        def randomized_quicksort(nums, l, r):\n",
    "            if l >= r:\n",
    "                return nums\n",
    "            pos = random_partition(nums, l, r)\n",
    "            randomized_quicksort(nums, l, pos - 1)\n",
    "            randomized_quicksort(nums, pos + 1, r)\n",
    "            return nums\n",
    "        def random_partition(nums, l, r):\n",
    "            import random\n",
    "            pos = random.randint(l, r)\n",
    "            swap(nums, r, pos)\n",
    "            return partition(nums, l, r)\n",
    "        def partition(nums, l, r):\n",
    "            pivot = nums[r]\n",
    "            i = l - 1\n",
    "            for j in range(l, r):\n",
    "                if nums[j] <= pivot:\n",
    "                    i += 1\n",
    "                    swap(nums, i, j)\n",
    "            swap(nums, i+1, r)\n",
    "            return i+1\n",
    "\n",
    "\n",
    "        l = 0\n",
    "        r = len(t_nums) - 1\n",
    "        t_ans = randomized_quicksort(t_nums, l, r)\n",
    "        ans = []\n",
    "        for i in t_ans:\n",
    "            if i in clean_d.keys():\n",
    "                for j in range(clean_d[i]):\n",
    "                    ans.append(i)\n",
    "            else:\n",
    "                ans.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def CountingSort(self, nums):\n",
    "        res = []\n",
    "        min_num = min(nums)\n",
    "        max_num = max(nums)\n",
    "        span = max_num - min_num + 1\n",
    "        count_arr = [0] * span\n",
    "        for num in nums:\n",
    "            count_arr[num - min_num] += 1\n",
    "        for i in range(span):\n",
    "            while count_arr[i] > 0:\n",
    "                res.append(i + min_num)\n",
    "                count_arr[i] -= 1\n",
    "        return res\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        max_num = max(nums)\n",
    "        min_num = min(nums)\n",
    "        Bucket_size = (max_num - min_num) // n + 1\n",
    "        Bucket_num = (max_num - min_num) // Bucket_size + 1\n",
    "        Buckets = [[] * Bucket_size for _ in range(Bucket_num)]\n",
    "        for num in nums:\n",
    "            Buckets[(num - min_num) // Bucket_size].append(num)\n",
    "        res = []\n",
    "        for Bucket in Buckets:\n",
    "            if Bucket:\n",
    "                res += self.CountingSort(Bucket)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def CountingSort(self, nums):\n",
    "        res = []\n",
    "        min_num = min(nums)\n",
    "        max_num = max(nums)\n",
    "        span = max_num - min_num + 1\n",
    "        count_arr = [0] * span\n",
    "        for num in nums:\n",
    "            count_arr[num - min_num] += 1\n",
    "        for i in range(span):\n",
    "            while count_arr[i] > 0:\n",
    "                res.append(i + min_num)\n",
    "                count_arr[i] -= 1\n",
    "        return res\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        max_num = max(nums)\n",
    "        min_num = min(nums)\n",
    "        Bucket_size = (max_num - min_num) // n + 1\n",
    "        Bucket_num = (max_num - min_num) // Bucket_size + 1\n",
    "        Buckets = [[] for _ in range(Bucket_num)]\n",
    "        for num in nums:\n",
    "            Buckets[(num - min_num) // Bucket_size].append(num)\n",
    "        res = []\n",
    "        for Bucket in Buckets:\n",
    "            if Bucket:\n",
    "                res += self.CountingSort(Bucket)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, key):\n",
    "        self.key = key\n",
    "        self.degree = 0\n",
    "        self.child = None\n",
    "        self.brother = None\n",
    "        self.parent = None\n",
    "\n",
    "class BinomialHeap:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "    \n",
    "    @staticmethod\n",
    "    def _mergeList(h1, h2):\n",
    "        dummy = h = Node(0)\n",
    "        while True:\n",
    "            if not h1:\n",
    "                h.brother = h2\n",
    "                return dummy.brother\n",
    "            if not h2:\n",
    "                h.brother = h1\n",
    "                return dummy.brother\n",
    "            if h1.degree <= h2.degree:\n",
    "                h.brother = h1\n",
    "                h1 = h1.brother\n",
    "                h = h.brother\n",
    "            else:\n",
    "                h.brother = h2\n",
    "                h2 = h2.brother\n",
    "                h = h.brother\n",
    "    \n",
    "    @staticmethod\n",
    "    def _linkTree(prv):\n",
    "        if prv.brother.key < prv.brother.brother.key:\n",
    "            p = prv.brother\n",
    "            c = prv.brother.brother\n",
    "            p.brother = c.brother\n",
    "        else:\n",
    "            p = prv.brother.brother\n",
    "            c = prv.brother\n",
    "            prv.brother = p\n",
    "        c.brother = p.child\n",
    "        c.parent = p\n",
    "        p.child = c\n",
    "        p.degree += 1\n",
    "            \n",
    "    @classmethod\n",
    "    def _fixList(cls, h):\n",
    "        prv = dummy = Node(0)\n",
    "        prv.brother = h\n",
    "        while h:\n",
    "            if not h.brother:\n",
    "                return dummy.brother\n",
    "            elif h.degree < h.brother.degree:\n",
    "                prv, h = h, h.brother\n",
    "            elif not h.brother.brother:\n",
    "                cls._linkTree(prv)\n",
    "                return dummy.brother\n",
    "            elif h.brother.degree < h.brother.brother.degree:\n",
    "                cls._linkTree(prv)\n",
    "                h = prv.brother\n",
    "            else:\n",
    "                cls._linkTree(h)\n",
    "                prv, h = h, h.brother\n",
    "\n",
    "    @classmethod\n",
    "    def merge(cls, h1, h2):\n",
    "        return cls._fixList(cls._mergeList(h1, h2))\n",
    "    \n",
    "    def put(self, k):\n",
    "        self.head = self.merge(self.head, Node(k))\n",
    "    \n",
    "    @classmethod\n",
    "    def _reverseAndRemoveParent(cls, h):\n",
    "        if not h:\n",
    "            return None\n",
    "        h.parent = None\n",
    "        if not h.brother:\n",
    "            return h\n",
    "        hh = cls._reverseAndRemoveParent(h.brother)\n",
    "        h.brother.brother = h\n",
    "        h.brother = None\n",
    "        return hh\n",
    "    \n",
    "    @staticmethod\n",
    "    def _minimum(h):\n",
    "        targetPrev, target = None, h\n",
    "        prev = None\n",
    "        while h:\n",
    "            if h.key < target.key:\n",
    "                targetPrev, target = prev, h\n",
    "            prev, h = h, h.brother\n",
    "        return targetPrev, target\n",
    "    \n",
    "    def get(self):\n",
    "        assert self.head\n",
    "        prv, r = self._minimum(self.head)\n",
    "        if prv:\n",
    "            prv.brother = r.brother\n",
    "        else:\n",
    "            self.head = r.brother\n",
    "        h = self._reverseAndRemoveParent(r.child)\n",
    "        self.head = self.merge(self.head, h)\n",
    "        return r.key\n",
    "    \n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        h = BinomialHeap()\n",
    "        result = []\n",
    "        while nums:\n",
    "            h.put(nums.pop())\n",
    "        while h.head:\n",
    "            result.append(h.get())\n",
    "        return result\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        current=collections.Counter(nums)\n",
    "        current=sorted(current.items(),key=lambda item:item[0])\n",
    "        re=[]\n",
    "        for key,value in current:\n",
    "            re+=[key]*value\n",
    "        # print(re)\n",
    "        return re\n",
    "        # # 快速排序 \n",
    "        # def partion(nums,i,j):\n",
    "        #     tmp=nums[i]\n",
    "        #     # left,right=i,j\n",
    "        #     while i<j:\n",
    "        #         while nums[j]>=tmp and i<j:\n",
    "        #             j-=1\n",
    "        #         nums[i]=nums[j]\n",
    "        #         while nums[i]<=tmp and i<j:\n",
    "        #             i+=1\n",
    "        #         nums[j]=nums[i]\n",
    "        #     nums[i]=tmp\n",
    "        #     return i \n",
    "        \n",
    "        #     # quicksort(nums,left,i-1)\n",
    "        #     # quicksort(nums,i+1,right)\n",
    "        # def quick_sort_single(arr,l,r):\n",
    "        #     if l<r:\n",
    "        #         k=partion(arr,l,r)\n",
    "        #         quick_sort_single(arr,l,k-1)\n",
    "        #         quick_sort_single(arr,k+1,r)\n",
    "        #     return arr\n",
    "        # return quick_sort_single(nums,0,len(nums)-1)\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, arr: List[int]) -> List[int]:\n",
    "        return counting_sort(arr)\n",
    "\n",
    "def counting_sort(nums: List[int]) -> List[int]:\n",
    "    # 借助 Counter进行排序\n",
    "    cnt = collections.Counter(nums)\n",
    "    res = []\n",
    "    for num, freq in sorted(cnt.items(), key=lambda x: x[0]):\n",
    "        res += [num] * freq\n",
    "    \n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def sortArray(self, nums):\n",
    "        def quicksort(l, r):\n",
    "            if l >= r:\n",
    "                return\n",
    "            pivot = nums[random.randint(l, r)]\n",
    "            li, ri = l, r\n",
    "            while li <= ri:\n",
    "                if nums[li] >= pivot > nums[ri] or nums[li] > pivot >= nums[ri]:\n",
    "                    nums[li], nums[ri] = nums[ri], nums[li]\n",
    "                li += (nums[li] <= pivot)\n",
    "                ri -= (nums[ri] >= pivot)\n",
    "                \n",
    "            quicksort(l, ri)\n",
    "            quicksort(li, r)\n",
    "\n",
    "        quicksort(0, len(nums)-1)\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        def quicksort(left,right):\n",
    "            if left>=right:\n",
    "                return\n",
    "            pivot=nums[left]\n",
    "            l=left\n",
    "            r=right\n",
    "            while l<r:\n",
    "                while l<r and nums[r]>=pivot:\n",
    "                    r-=1\n",
    "                nums[l]=nums[r]\n",
    "                while l<r and nums[l]<pivot:\n",
    "                    l+=1\n",
    "                nums[r]=nums[l]\n",
    "            nums[l]=pivot\n",
    "            quicksort(left,l-1)\n",
    "            quicksort(l+1,right)\n",
    "        def merge(left,right,mid):\n",
    "            l=left\n",
    "            r=mid+1\n",
    "            temp=[]\n",
    "            while l<=mid and r<=right:\n",
    "                if nums[l]<=nums[r]:\n",
    "                    temp.append(nums[l])\n",
    "                    l+=1\n",
    "                else:\n",
    "                    temp.append(nums[r])\n",
    "                    r+=1\n",
    "            while l<=mid:\n",
    "                temp.append(nums[l])\n",
    "                l+=1\n",
    "            while r<=right:\n",
    "                temp.append(nums[r])\n",
    "                r+=1\n",
    "            for i in range(left,right+1):\n",
    "                nums[i]=temp[i-left]\n",
    "            \n",
    "        def mergesort(left,right):\n",
    "            if left>=right:\n",
    "                return\n",
    "            mid=(left+right)//2\n",
    "            mergesort(left,mid)\n",
    "            mergesort(mid+1,right)\n",
    "            merge(left,right,mid)\n",
    "        mergesort(0,len(nums)-1)\n",
    "        return nums\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        def merge_sort(l, r):\n",
    "            if l >= r:\n",
    "                return\n",
    "            mid = (l + r) >> 1\n",
    "            merge_sort(l, mid)\n",
    "            merge_sort(mid + 1, r)\n",
    "            i, j = l, mid + 1\n",
    "            tmp = []\n",
    "            while i <= mid and j <= r:\n",
    "                if nums[i] <= nums[j]:\n",
    "                    tmp.append(nums[i])\n",
    "                    i += 1\n",
    "                else:\n",
    "                    tmp.append(nums[j])\n",
    "                    j += 1\n",
    "            if i <= mid:\n",
    "                tmp.extend(nums[i:mid + 1])\n",
    "            if j <= r:\n",
    "                tmp.extend(nums[j: r + 1])\n",
    "            for i in range(l, r + 1):\n",
    "                nums[i] = tmp[i - l]\n",
    "        \n",
    "        merge_sort(0, len(nums) - 1)\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.tmp = []\n",
    "\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        # 冒泡排序，复杂度：O(n^2)，铁定超时\n",
    "        # for i in range(1, len(nums)):\n",
    "        #     for j in range(0, len(nums) - i):\n",
    "        #         if nums[j] > nums[j + 1]:\n",
    "        #             nums[j], nums[j + 1] = nums[j + 1], nums[j]\n",
    "        # return nums\n",
    "\n",
    "        # 归并排序 O(NlogN)\n",
    "        def sort(nums, lo, hi):\n",
    "            # base case, 单个元素时候不用排序\n",
    "            if lo == hi:\n",
    "                return\n",
    "\n",
    "            mid = lo + (hi - lo) // 2\n",
    "\n",
    "            # 对左半排序\n",
    "            sort(nums, lo, mid)\n",
    "            # 对右半排序\n",
    "            sort(nums, mid + 1, hi)\n",
    "\n",
    "            # 排序并合并\n",
    "            merge(nums, lo, mid, hi)\n",
    "\n",
    "        # 完成排序和合并动作\n",
    "        def merge(nums, lo, mid, hi):\n",
    "            # 复制原数组到辅助数组\n",
    "            for i in range(lo, hi + 1):\n",
    "                self.tmp[i] = nums[i]\n",
    "\n",
    "            # 双指针法处理\n",
    "            i = lo\n",
    "            j = mid + 1\n",
    "            for p in range(lo, hi + 1):\n",
    "                # 左半处理完成\n",
    "                if i == (mid + 1):\n",
    "                    nums[p] = self.tmp[j]\n",
    "                    j += 1\n",
    "                # 右半处理完成\n",
    "                elif j == (hi + 1):\n",
    "                    nums[p] = self.tmp[i]\n",
    "                    i += 1\n",
    "                elif self.tmp[i] > self.tmp[j]:\n",
    "                    nums[p] = self.tmp[j]\n",
    "                    j += 1\n",
    "                else:\n",
    "                    nums[p] = self.tmp[i]\n",
    "                    i += 1\n",
    "                p += 1\n",
    "\n",
    "        # 初始化辅助数组大小\n",
    "        self.tmp = [None] * len(nums)  \n",
    "        sort(nums, 0, len(nums) - 1)\n",
    "        return nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        # 归并排序\n",
    "        dst = [0] * len(nums)\n",
    "        def mergeSort(nums,l,r):\n",
    "            if r-l<=1:\n",
    "                return\n",
    "            m = (l+r)//2\n",
    "            mergeSort(nums,l,m)\n",
    "            mergeSort(nums,m,r)\n",
    "\n",
    "            i,j = l,m\n",
    "            for k in range(l,r):\n",
    "                if j==r or (i<m and nums[i]<nums[j]):\n",
    "                    dst[k] = nums[i]\n",
    "                    i+=1\n",
    "                else:\n",
    "                    dst[k] = nums[j]\n",
    "                    j+=1\n",
    "            for k in range(l,r):\n",
    "                nums[k] = dst[k]\n",
    "        mergeSort(nums,0,len(nums))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def swap(self, nums, i, j):\n",
    "        nums[i] ^= nums[j]\n",
    "        nums[j] ^= nums[i]\n",
    "        nums[i] ^= nums[j]\n",
    "    def swap2(self, nums, i, j):\n",
    "        temp = nums[i]\n",
    "        nums[i] = nums[j]\n",
    "        nums[j] = temp\n",
    "\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        if not nums or len(nums) == 1:\n",
    "            return nums\n",
    "        return self.quickSort(nums)\n",
    "\n",
    "    def quickSort(self, nums):\n",
    "        def partition(L, R):\n",
    "            if L >= R:\n",
    "                return\n",
    "            idx = random.randint(L, R)\n",
    "            pivot = nums[idx]\n",
    "            self.swap2(nums, R, idx)\n",
    "            l, r = L, R\n",
    "            i = l\n",
    "            while r >= i:\n",
    "                val = nums[i]\n",
    "                if val < pivot:\n",
    "                    self.swap2(nums, i, l)\n",
    "                    i += 1\n",
    "                    l += 1\n",
    "                elif val == pivot:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    self.swap2(nums, i, r)\n",
    "                    r -= 1\n",
    "            partition(L, l - 1)\n",
    "            partition(r, R)\n",
    "\n",
    "        partition(0, len(nums) - 1)\n",
    "        return nums\n",
    "\n",
    "    \n",
    "    def bubbleSort(self, nums):\n",
    "        N = len(nums)\n",
    "        for i in range(N - 1):\n",
    "            for j in range(i + 1, N):\n",
    "                if nums[i] > nums[j]:\n",
    "                    self.swap(nums, i, j)\n",
    "        return nums\n",
    "    \n",
    "    def mergeSort(self, nums):\n",
    "        def partition(nums, L, R):\n",
    "            if L >= R:\n",
    "                return\n",
    "            m = L + (R - L) // 2\n",
    "            partition(nums, L, m)\n",
    "            partition(nums, m + 1, R)\n",
    "            merge(nums, L, R, m)\n",
    "        def merge(nums, L, R, M):\n",
    "            helper = []\n",
    "            l, r = L, M + 1\n",
    "            while l <= M and r <= R:\n",
    "                v1, v2 = nums[l], nums[r]\n",
    "                if v1 <= v2:\n",
    "                    helper.append(v1)\n",
    "                    l += 1\n",
    "                else:\n",
    "                    helper.append(v2)\n",
    "                    r += 1\n",
    "            if l <= M:\n",
    "                helper.extend(nums[l : M + 1])\n",
    "            elif r <= R:\n",
    "                helper.extend(nums[r : ])\n",
    "            j = 0\n",
    "            for i in range(L, R + 1):\n",
    "                nums[i] = helper[j]\n",
    "                j += 1\n",
    "        partition(nums, 0, len(nums) - 1)\n",
    "        return nums\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        # 快排方式，通过随机数确定pos，递归调用左右子序列，注意停止条件（之前有个bug，如rt=low+1时左边停止，但右边还是要继续递归的），当返回位置为low或low+1时左边停止，返回位置为high或high-1时右边停止。\n",
    "        def qsort(low:int, high:int) -> None:\n",
    "            if low == high:\n",
    "                return\n",
    "            #pos = random.randint(low, high);\n",
    "            rt = partition(random.randint(low, high), low, high);\n",
    "            if rt > low+1:\n",
    "                # 添加判断，避免大量重复值时性能退化，缩小递归范围\n",
    "                while rt > low+1 and nums[rt] == nums[rt-1]:\n",
    "                    rt -= 1; \n",
    "                qsort(low, rt-1);\n",
    "            if rt < high-1:\n",
    "                while rt < high-1 and nums[rt] == nums[rt+1]:\n",
    "                    rt += 1; \n",
    "                qsort(rt+1, high);\n",
    "\n",
    "        # 一次快排过程：将pos值对调到low位置，双指针分别从前后两个方向遍历比较，从后往前遇到小于pos的移动，从前往后遇到大于pos的移动，最终low=high，将pos值赋给相遇位置，返回相遇位置，得到左小+pos+右大的序列\n",
    "        def partition(pos:int, low:int, high:int) -> int:\n",
    "            tar = nums[pos];\n",
    "            nums[low], nums[pos] = nums[pos], nums[low];\n",
    "            while low < high:\n",
    "                # 从后往前，小于pos的移到前面坑位，空出新的high坑位\n",
    "                while high > low and nums[high] >= tar:\n",
    "                    high -= 1;\n",
    "                nums[low] = nums[high];\n",
    "                # 从前往后，大于pos的移到后面刚high的坑位，空出新的left坑位\n",
    "                while low < high and nums[low] <= tar:\n",
    "                    low += 1;\n",
    "                nums[high] = nums[low];\n",
    "            nums[low] = tar;\n",
    "            return low;\n",
    "        \n",
    "        if len(nums) == 1:\n",
    "            return nums;\n",
    "        n = len(nums);\n",
    "        qsort(0, n-1);\n",
    "        return nums;\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        # 快排方式，通过随机数确定pos，递归调用左右子序列，注意停止条件，当返回位置为low或low+1时左边停止，返回位置为high或high-1时右边停止。\n",
    "        def qsort(low:int, high:int) -> None:\n",
    "            if low == high:\n",
    "                return\n",
    "            pos = random.randint(low, high)\n",
    "            rt = partition(pos, low, high)\n",
    "            if rt > low+1:\n",
    "                # 添加判断，避免大量重复值时性能退化，缩小递归范围\n",
    "                while rt > low+1 and nums[rt] == nums[rt-1]:\n",
    "                    rt -= 1; \n",
    "                qsort(low, rt-1)\n",
    "            if rt < high-1:\n",
    "                while rt < high-1 and nums[rt] == nums[rt+1]:\n",
    "                    rt += 1; \n",
    "                qsort(rt+1, high)\n",
    "\n",
    "        # 一次快排过程：将pos值对调到low位置，双指针分别从前后两个方向遍历比较，从后往前遇到小于pos的移动，从前往后遇到大于pos的移动，最终low=high，将pos值赋给相遇位置，返回相遇位置，得到左小+pos+右大的序列\n",
    "        def partition(pos:int, low:int, high:int) -> int:\n",
    "            tar = nums[pos]\n",
    "            nums[low], nums[pos] = nums[pos], nums[low]\n",
    "            while low < high:\n",
    "                # 从后往前，小于pos的移到前面坑位，空出新的high坑位\n",
    "                while high > low and nums[high] >= tar:\n",
    "                    high -= 1\n",
    "                nums[low] = nums[high]\n",
    "                # 从前往后，大于pos的移到后面刚high的坑位，空出新的left坑位\n",
    "                while low < high and nums[low] <= tar:\n",
    "                    low += 1\n",
    "                nums[high] = nums[low]\n",
    "            nums[low] = tar\n",
    "            return low\n",
    "        \n",
    "        if len(nums) == 1:\n",
    "            return nums\n",
    "        n = len(nums)\n",
    "        qsort(0, n-1)\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        \n",
    "        def getMid(a, b, c):\n",
    "            max_value = max(a, b, c)\n",
    "            min_value = min(a, b, c)\n",
    "\n",
    "            middle_value = a + b + c - max_value - min_value\n",
    "            return middle_value\n",
    "        \n",
    "        def fun(nums, x, y):\n",
    "            l, r = x, y\n",
    "            if l >= r:\n",
    "                return\n",
    "            base = getMid(nums[l], nums[(l+r)//2], nums[r])\n",
    "            while l <= r:\n",
    "                while nums[r] > base and l <= r:\n",
    "                    r -= 1\n",
    "                while nums[l] < base and l <= r:\n",
    "                    l += 1\n",
    "                if l <= r:\n",
    "                    nums[l], nums[r] = nums[r], nums[l]\n",
    "                    l += 1\n",
    "                    r -= 1\n",
    "\n",
    "            fun(nums, x, r)\n",
    "            fun(nums, l, y)\n",
    "\n",
    "        n = len(nums)\n",
    "        fun(nums, 0, n-1)\n",
    "\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        \n",
    "        def getMid(a, b, c):\n",
    "            max_value = max(a, b, c)\n",
    "            min_value = min(a, b, c)\n",
    "\n",
    "            middle_value = a + b + c - max_value - min_value\n",
    "            return middle_value\n",
    "        \n",
    "        def fun(nums, x, y):\n",
    "            l, r = x, y\n",
    "            if l >= r:\n",
    "                return\n",
    "            base = getMid(nums[l], nums[(l+r)//2], nums[r])\n",
    "            while l <= r:\n",
    "                while nums[r] > base and l <= r:\n",
    "                    r -= 1\n",
    "                while nums[l] < base and l <= r:\n",
    "                    l += 1\n",
    "                if l <= r:\n",
    "                    nums[l], nums[r] = nums[r], nums[l]\n",
    "                    l += 1\n",
    "                    r -= 1\n",
    "\n",
    "            fun(nums, x, r)\n",
    "            fun(nums, l, y)\n",
    "\n",
    "        n = len(nums)\n",
    "        fun(nums, 0, n-1)\n",
    "\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from random import randint\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "\n",
    "        def quickSort(l, r):\n",
    "            if l >= r:\n",
    "                return\n",
    "            \n",
    "            x = nums[random.randint(l, r)]\n",
    "            i, j = l - 1, r + 1\n",
    "            while i < j:\n",
    "                i += 1\n",
    "                while nums[i] <x:\n",
    "                    i += 1\n",
    "                j -= 1\n",
    "                while nums[j] > x:\n",
    "                    j -= 1\n",
    "                if i < j:\n",
    "                    nums[i], nums[j] = nums[j], nums[i]\n",
    "            quickSort(l, j)\n",
    "            quickSort(j + 1, r)\n",
    "        quickSort(0, len(nums) - 1)\n",
    "        return nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        def quick_sort(q,l,r):\n",
    "            if l>=r:\n",
    "                return\n",
    "            x=q[l]+q[r]+q[(l+r)//2]-max(q[l],q[r],q[(l+r)//2])-min(q[l],q[r],q[(l+r)//2])\n",
    "            i=l-1;j=r+1\n",
    "            while i<j:\n",
    "                while True:\n",
    "                    i+=1\n",
    "                    if(q[i]>=x):break\n",
    "                while True:\n",
    "                    j-=1\n",
    "                    if(q[j]<=x):break\n",
    "                if i<j:q[i],q[j]=q[j],q[i]\n",
    "            quick_sort(q,l,j)\n",
    "            quick_sort(q,j+1,r)\n",
    "        \n",
    "        quick_sort(nums,0,len(nums)-1)\n",
    "        return nums\n",
    "    \n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        def quick(data, left, right):\n",
    "            if left >= right:\n",
    "                return\n",
    "            pivot = random.randint(left, right)\n",
    "            nums[left], nums[pivot] = nums[pivot], nums[left]\n",
    "            l, r = left+1, right\n",
    "            i = left+1\n",
    "            while i <= r:\n",
    "                if nums[i] < nums[left]:\n",
    "                    nums[i], nums[l] = nums[l], nums[i]\n",
    "                    l += 1\n",
    "                    i += 1\n",
    "                elif nums[i] > nums[left]:\n",
    "                    nums[i], nums[r] = nums[r], nums[i]\n",
    "                    r -= 1\n",
    "                else:\n",
    "                    i += 1\n",
    "            nums[left], nums[l-1] = nums[l-1], nums[left]\n",
    "            quick(data, left, l-1)\n",
    "            quick(data, r+1, right)\n",
    "        quick(nums, 0, len(nums)-1)\n",
    "        return nums\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # def quick(left, right):\n",
    "        #     if left >= right:\n",
    "        #         return \n",
    "        #     pivot = random.randint(left, right)\n",
    "        #     nums[left], nums[pivot] = nums[pivot], nums[left]\n",
    "        #     i, l, r = left+1, left+1, right\n",
    "        #     while i <= r:\n",
    "        #         if nums[i] > nums[left]:\n",
    "        #             nums[i], nums[r] = nums[r], nums[i]\n",
    "        #             r -= 1\n",
    "        #         elif nums[i] < nums[left]:\n",
    "        #             nums[i], nums[l] = nums[l], nums[i]\n",
    "        #             i += 1\n",
    "        #             l += 1\n",
    "        #         else:\n",
    "        #             i += 1\n",
    "        #     nums[left], nums[l-1] = nums[l-1], nums[left]\n",
    "        #     quick(left, l-2)\n",
    "        #     quick(r+1, right)\n",
    "        # quick(0, len(nums)-1)\n",
    "        # return nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    " def sortArray(self, nums: List[int]) -> List[int]:\n",
    "    # MergeSort解法: 递归将数组从中间分为2部分，然后写一个合并函数，用来合并2个有序数组，返回一个有序数组\n",
    "\n",
    "    # tmp辅助数组，用来复制原始数组元素和索引位置\n",
    "    tmp = [0] * len(nums)\n",
    "\n",
    "    # i = 0\n",
    "\n",
    "    def mergeSort(nums, left, right) -> None:\n",
    "        # 分：将nums按照索引递归分成[left...mid] 和[mid+1, right]两部分，后续位置调用merge函数，无返回值。\n",
    "        if left == right:  # 只有1个元素，就不用排序，直接返回\n",
    "            return\n",
    "\n",
    "        mid = (right + left) // 2  # 向下取整，可以保证mid+1不越界\n",
    "\n",
    "        mergeSort(nums, left, mid)\n",
    "        mergeSort(nums, mid + 1, right)\n",
    "\n",
    "        # todo 二叉树后续位置\n",
    "        # 优化：如果左数组最大值小于右数组最小值，就可以直接归并2个数组\n",
    "        if nums[mid] <= nums[mid + 1]:\n",
    "            return\n",
    "        else:\n",
    "            # nonlocal i\n",
    "            # i += 1\n",
    "            # print(f'\\n第{i}次递归')\n",
    "            # print(f'merge前nums为：{nums}')\n",
    "            mergeTwoSortedArr(nums, left, mid, right)\n",
    "            # print(f'merge后nums为：{nums}')\n",
    "\n",
    "    def mergeTwoSortedArr(nums, left, mid, right) -> None:\n",
    "        # 先把 nums[lo..hi] 复制到辅助数组中\n",
    "        # 以便合并后的结果能够直接存入 nums\n",
    "        for i in range(left, right + 1):\n",
    "            tmp[i] = nums[i]\n",
    "\n",
    "        # 数组双指针技巧，合并两个有序数组:\n",
    "        # i指向[left..mid]，j指向[mid+1..right], k指向原始数组索引nums[left..right]\n",
    "        i, j = left, mid + 1\n",
    "        for k in range(left, right + 1):\n",
    "            if i == mid + 1:\n",
    "                # 左边数组放完了\n",
    "                nums[k] = tmp[j]\n",
    "                j += 1\n",
    "            elif j == right + 1:\n",
    "                # 右边数组放完了\n",
    "                nums[k] = tmp[i]\n",
    "                i += 1\n",
    "            # 下面2步是让原始数组nums[k]每次存储左右数组中较小的那个\n",
    "            elif tmp[i] <= tmp[j]:  # 这里写等于，是为了保障排序之后，相同元素的位置稳定性\n",
    "                nums[k] = tmp[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                nums[k] = tmp[j]\n",
    "                j += 1\n",
    "\n",
    "    mergeSort(nums, 0, len(nums) - 1)\n",
    "    return nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    " def sortArray(self, nums: List[int]) -> List[int]:\n",
    "    # MergeSort解法: 递归将数组从中间分为2部分，然后写一个合并函数，用来合并2个有序数组，返回一个有序数组\n",
    "\n",
    "    # tmp辅助数组，用来复制原始数组元素和索引位置\n",
    "    tmp = [0] * len(nums)\n",
    "    # tmp = nums.copy()\n",
    "\n",
    "    # i = 0\n",
    "\n",
    "    def mergeSort(nums, left, right) -> None:\n",
    "        # 分：将nums按照索引递归分成[left...mid] 和[mid+1, right]两部分，后续位置调用merge函数，无返回值。\n",
    "        if left == right:  # 只有1个元素，就不用排序，直接返回\n",
    "            return\n",
    "\n",
    "        mid = (right + left) // 2  # 向下取整，可以保证mid+1不越界\n",
    "\n",
    "        mergeSort(nums, left, mid)\n",
    "        mergeSort(nums, mid + 1, right)\n",
    "\n",
    "        # todo 二叉树后续位置\n",
    "        # 优化：如果左数组最大值小于右数组最小值，就可以直接归并2个数组\n",
    "        if nums[mid] <= nums[mid + 1]:\n",
    "            return\n",
    "        else:\n",
    "            # nonlocal i\n",
    "            # i += 1\n",
    "            # print(f'\\n第{i}次递归')\n",
    "            # print(f'merge前nums为：{nums}')\n",
    "            mergeTwoSortedArr(nums, left, mid, right)\n",
    "            # print(f'merge后nums为：{nums}')\n",
    "\n",
    "    def mergeTwoSortedArr(nums, left, mid, right) -> None:\n",
    "        # 先把 nums[lo..hi] 复制到辅助数组中\n",
    "        # 以便合并后的结果能够直接存入 nums\n",
    "        for i in range(left, right + 1):\n",
    "            tmp[i] = nums[i]\n",
    "\n",
    "        # 数组双指针技巧，合并两个有序数组:\n",
    "        # i指向[left..mid]，j指向[mid+1..right], k指向原始数组索引nums[left..right]\n",
    "        i, j = left, mid + 1\n",
    "        for k in range(left, right + 1):\n",
    "            if i == mid + 1:\n",
    "                # 左边数组放完了\n",
    "                nums[k] = tmp[j]\n",
    "                j += 1\n",
    "            elif j == right + 1:\n",
    "                # 右边数组放完了\n",
    "                nums[k] = tmp[i]\n",
    "                i += 1\n",
    "            # 下面2步是让原始数组nums[k]每次存储左右数组中较小的那个\n",
    "            elif tmp[i] <= tmp[j]:  # 这里写等于，是为了保障排序之后，相同元素的位置稳定性\n",
    "                nums[k] = tmp[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                nums[k] = tmp[j]\n",
    "                j += 1\n",
    "\n",
    "    mergeSort(nums, 0, len(nums) - 1)\n",
    "    return nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        def partition(low, high):\n",
    "            pivot = random.randint(low, high)\n",
    "            nums[low], nums[pivot] = nums[pivot], nums[low]\n",
    "            i, j = low, low + 1\n",
    "            count = 0\n",
    "\n",
    "            while j <= high:#j loop indicator, i之前包括i的已经排好\n",
    "                if nums[j] < nums[low]: #如果发现遍历的到的数小于low指向的（pivot）\n",
    "                    nums[i + 1], nums[j] = nums[j], nums[i + 1] #把它与i+1指向的交换，并且i进一位。因为i指向的是排好的，i+1是没排好的\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                elif nums[j] == nums[low]:\n",
    "                    count +=1\n",
    "                    high -=1\n",
    "                    del nums[j]\n",
    "                else:\n",
    "                    j += 1\n",
    "                \n",
    "            nums[low], nums[i] = nums[i], nums[low] #最后把i指向的和pivot交换\n",
    "            for i_count in range(count):\n",
    "                nums.insert(i+1, nums[i])\n",
    "            \n",
    "            \n",
    "            return (i,i+count)\n",
    "            \n",
    "        def quick_sort(low, high):\n",
    "            if low < high:\n",
    "                mid1,mid2 = partition(low, high)\n",
    "                quick_sort(low, mid1 - 1)\n",
    "                quick_sort(mid2 + 1, high)\n",
    "        \n",
    "        quick_sort(0, len(nums) - 1)\n",
    "        return nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import random\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        def quick_sort(arr, low, high):\n",
    "            def random_pivot(low, high):\n",
    "                return random.randint(low, high)\n",
    "            \n",
    "            def middle_num(arr, low, high):\n",
    "                def get_middle(a, b, c):\n",
    "                    middle = a\n",
    "                    if (b-a)*(b-c) <= 0:\n",
    "                        middle = b\n",
    "                    if (c-a)*(c-b) <= 0:\n",
    "                        middle = c\n",
    "                    return middle\n",
    "                mid = low + ((high - low) >> 1)\n",
    "                num = {arr[low]:low, arr[high]:high, arr[mid]:mid}\n",
    "                return num[get_middle(arr[low], arr[high], arr[mid])]\n",
    "            \n",
    "            def partation(arr, low, high): \n",
    "                # pivot_idx = random_pivot(low, high)\n",
    "                pivot_idx = middle_num(arr, low, high)\n",
    "                arr[low], arr[pivot_idx] = arr[pivot_idx], arr[low]\n",
    "                pivot = arr[low]\n",
    "                while low < high:\n",
    "                    while low < high and arr[high] >= pivot:\n",
    "                        high -= 1\n",
    "                    arr[low] = arr[high]\n",
    "                    while low < high and arr[low] <= pivot:\n",
    "                        low += 1\n",
    "                    arr[high] = arr[low]\n",
    "                arr[low] = pivot\n",
    "                return low\n",
    "\n",
    "            if low >= high:\n",
    "                return\n",
    "            pivot = partation(arr, low, high)\n",
    "            # 左移pivot位置，减少递归范围\n",
    "            if pivot > low + 1:\n",
    "                while pivot > low + 1 and arr[pivot] == arr[pivot - 1]:\n",
    "                    pivot -= 1\n",
    "                quick_sort(arr, low, pivot-1)\n",
    "            # 右移pivot位置，减少递归范围\n",
    "            if pivot < high - 1:\n",
    "                while pivot < high - 1 and arr[pivot] == arr[pivot + 1]:\n",
    "                    pivot += 1\n",
    "                quick_sort(arr, pivot+1, high)\n",
    "\n",
    "        low = 0\n",
    "        high = len(nums) - 1\n",
    "        quick_sort(nums, low, high)\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        def merge_sort(nums, left, right):\n",
    "            if left >= right: return \n",
    "            mid = left + right >> 1\n",
    "            merge_sort(nums, left, mid)\n",
    "            merge_sort(nums, mid + 1, right)\n",
    "\n",
    "            i, j, k = left, mid + 1, 0\n",
    "            while i <= mid and j <= right:\n",
    "                if (nums[i] <= nums[j]): \n",
    "                    tmp[k] = nums[i]\n",
    "                    i += 1\n",
    "                else:\n",
    "                    tmp[k] = nums[j]\n",
    "                    j += 1\n",
    "                k += 1\n",
    "            \n",
    "            while i <= mid:\n",
    "                tmp[k] = nums[i]\n",
    "                i += 1\n",
    "                k += 1\n",
    "            while j <= right:\n",
    "                tmp[k] = nums[j]\n",
    "                j += 1\n",
    "                k += 1\n",
    "            for i in range(right - left + 1):\n",
    "                nums[i + left] = tmp[i]\n",
    "\n",
    "        tmp = [0] * len(nums)\n",
    "        left, right = 0, len(nums) - 1\n",
    "        merge_sort(nums, left, right)\n",
    "        return nums\n",
    "\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        def mergeSort(array, L, R):\n",
    "            if L == R:\n",
    "                return array\n",
    "            m = (L + R) // 2\n",
    "            mergeSort(array, L, m)\n",
    "            mergeSort(array, m + 1, R)\n",
    "            merge(array, L, m, R)\n",
    "            return array\n",
    "\n",
    "        def merge(array, L, M, R):\n",
    "            left = array[L : M + 1]\n",
    "            right = array[M + 1 : R + 1]\n",
    "\n",
    "            point_array, point_left, point_right = L, 0, 0\n",
    "\n",
    "            while point_left < len(left) and point_right < len(right):\n",
    "                if left[point_left] <= right[point_right]:\n",
    "                    array[point_array] = left[point_left]\n",
    "                    point_left += 1\n",
    "                else:\n",
    "                    array[point_array] = right[point_right]\n",
    "                    point_right += 1\n",
    "                point_array += 1\n",
    "            while point_left < len(left):\n",
    "                nums[point_array] = left[point_left]\n",
    "                point_left += 1\n",
    "                point_array += 1\n",
    "            while point_right < len(right):\n",
    "                nums[point_array] = right[point_right]\n",
    "                point_right += 1\n",
    "                point_array += 1\n",
    "\n",
    "        return mergeSort(nums, 0, len(nums) - 1)\n",
    "\n",
    "# class Solution:\n",
    "#     def sortArray(self, arr: List[int]) -> List[int]:\n",
    "#         def mergeSort(arr):\n",
    "#             if len(arr) <= 1:\n",
    "#                 return arr\n",
    "#             mid = len(arr) // 2\n",
    "#             left = arr[:mid]\n",
    "#             right = arr[mid:]\n",
    "#             mergeSort(left)\n",
    "#             mergeSort(right)\n",
    "#             mergeInplace(arr, left, right)\n",
    "#             return arr\n",
    "\n",
    "#         def mergeInplace(arr, left, right):\n",
    "#             i = j = k = 0\n",
    "#             while i < len(left) and j < len(right):\n",
    "#                 if left[i] <= right[j]:\n",
    "#                     arr[k] = left[i]\n",
    "#                     i += 1\n",
    "#                 else:\n",
    "#                     arr[k] = right[j]\n",
    "#                     j += 1\n",
    "#                 k += 1\n",
    "#             while i < len(left):\n",
    "#                 arr[k] = left[i]\n",
    "#                 i += 1\n",
    "#                 k += 1\n",
    "#             while j < len(right):\n",
    "#                 arr[k] = right[j]\n",
    "#                 j += 1\n",
    "#                 k += 1\n",
    "\n",
    "#         return mergeSort(arr)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        def merge(l1: int, r1: int, l2: int, r2: int) -> List[int]:\n",
    "            # time complexity: O(N)\n",
    "            tmp = nums[l1 : r2 + 1]\n",
    "            x = l1\n",
    "            l1, r1 = 0, r1 - l1\n",
    "            l2, r2 = r1 + 1, r2 - x  # the previous l1\n",
    "\n",
    "            while l1 <= r1 or l2 <= r2:\n",
    "                if l1 <= r1 and l2 <= r2:\n",
    "                    if tmp[l1] < tmp[l2]:\n",
    "                        nums[x] = tmp[l1]\n",
    "                        l1 += 1\n",
    "                    else:\n",
    "                        nums[x] = tmp[l2]\n",
    "                        l2 += 1\n",
    "                elif l1 <= r1:\n",
    "                    nums[x] = tmp[l1]\n",
    "                    l1 += 1\n",
    "                elif l2 <= r2:\n",
    "                    nums[x] = tmp[l2]\n",
    "                    l2 += 1\n",
    "                x += 1\n",
    "\n",
    "        def merge_sort_range(l: int, r: int) -> List[int]:\n",
    "            # time complexity: O(log N)\n",
    "            if l == r:\n",
    "                return [nums[l]]\n",
    "            # devide\n",
    "            mid = (l + r) >> 1\n",
    "            # left part\n",
    "            merge_sort_range(l, mid)\n",
    "            # right part\n",
    "            merge_sort_range(mid + 1, r)\n",
    "            merge(l, mid, mid + 1, r)\n",
    "\n",
    "        merge_sort_range(0, len(nums) - 1)\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        def merge(arr,L,M,R):\n",
    "            left,right=arr[L:M+1],arr[M+1:R+1]\n",
    "            i,j,k=L,0,0\n",
    "            while j<len(left) and k<len(right):\n",
    "                if left[j]<=right[k]:\n",
    "                    arr[i]=left[j]\n",
    "                    j += 1\n",
    "                else:\n",
    "                    arr[i]=right[k]\n",
    "                    k += 1\n",
    "                i += 1      \n",
    "            while j<len(left):\n",
    "                nums[i]=left[j]\n",
    "                j += 1\n",
    "                i += 1\n",
    "            while k<len(right):\n",
    "                nums[i]=right[k]\n",
    "                k += 1  \n",
    "                i += 1\n",
    "        def mergesort(arr,l,r):\n",
    "            if l==r:\n",
    "                return arr\n",
    "            m=(l+r)//2\n",
    "            mergesort(arr,l,m)\n",
    "            mergesort(arr,m+1,r)\n",
    "            merge(arr,l,m,r)\n",
    "            return arr\n",
    "        return mergesort(nums,0,len(nums)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import random\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sortArray(self, nums: List[int]) -> List[int]:\n",
    "        #fast_sort\n",
    "        n = len(nums)\n",
    "        def backup(begin, end):\n",
    "            if begin >= end:\n",
    "                return\n",
    "            pviot = random.randint(begin, end)\n",
    "            left = begin\n",
    "            right = end\n",
    "            target = nums[pviot]\n",
    "            nums[begin], nums[pviot] = nums[pviot], nums[begin]\n",
    "            while left < right:\n",
    "                while left < right and nums[right] >= target:\n",
    "                    right -= 1\n",
    "                nums[left] = nums[right]\n",
    "                while left < right and nums[left] <= target:\n",
    "                    left += 1\n",
    "                nums[right] = nums[left]\n",
    "            nums[left] = target\n",
    "            while left > 0 and nums[left] == nums[left - 1]:\n",
    "                left -= 1\n",
    "            while right < n - 1 and nums[right] == nums[right + 1]:\n",
    "                right += 1\n",
    "            backup(begin, left - 1)\n",
    "            backup(right + 1, end)\n",
    "            return\n",
    "        backup(0, n - 1)\n",
    "\n",
    "\n",
    "        return nums\n",
    "        #heap_sort\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
